COMMENT ⊗   VALID 00028 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00004 00002	.DEVICE XGP
C00006 00003	.PORTION MACROS
C00010 00004	.ASEC(Summary)
C00013 00005	.NSECP(Theory)
C00023 00006	.SSEC(How to Build Such a System)
C00027 00007	.NSECP(Application to Automatic Programming)
C00035 00008	.SSEC(Details of the Experimental System)
C00052 00009	.SSSEC(The parts of a BEING)
C00059 00010	.SSSEC(Gaining Control)
C00065 00011	.SSSEC(Keeping the User Informed)
C00071 00012	.SSEC(Results)
C00080 00013	.SSSEC(How the BEINGs Interacted to Carry on that Dialogue)
C00092 00014	.SSSEC(The Range of Programs Synthesized by PUP6)
C00098 00015	.SSEC(Conclusions)
C00104 00016	.NSECP(Application to Mathematics Research)
C00108 00017	.SSEC(Ideas About Doing Mathematics)
C00113 00018	.SSEC(External Characteristics of a Proposed System)
C00126 00019	(v) The following diagram indicates the (traditional) logical progression
C00138 00020	.SSEC(Details of the Proposed System)
C00149 00021	.SSSEC(Interactions among system components)
C00162 00022	.SSSEC(Representation)
C00186 00023	.SSSEC(Communication)
C00196 00024	.SSEC(Projected Results)
C00200 00025	.SSSEC(A Hypothetical Session)
C00217 00026	.SSSEC(Synthesis)
C00219 00027	.ASEC(References)
C00227 00028	.EVERY HEADING(,,)
C00229 ENDMK
C⊗;
.DEVICE XGP

.FONT 1 "BASL30"
.FONT 2 "BASB30"
.FONT 4  "BASI30"
.FONT 5  "NGR40"
.FONT 6  "NGR25"
.FONT 7  "NGR20"
.FONT 8  "GRFX35"
.FONT 9  "FIX20"
.TURN ON "↑α↓_π[]{"
.TURN ON "⊗" FOR "%"
.TURN ON "@" FOR "%"
.PAGE FRAME 54 HIGH 89 WIDE
.TITLE AREA HEADING LINES 1 TO 2
.AREA TEXT LINES 4 TO 51  CHARS 1 TO 89
.NARROW 6,8
.TITLE AREA FOOTING LINES 53 TO 54
.COUNT PAGE PRINTING "1"
.TABBREAK
.ODDLEFTBORDER ← EVENLEFTBORDER ← 1000
.!XGPLFTMAR←110
.AT "ffi" ⊂ IF THISFONT ≤ 4 THEN "≠"  ELSE "fαfαi" ⊃;
.AT "ffl" ⊂ IF THISFONT ≤ 4 THEN "α∞" ELSE "fαfαl" ⊃;
.AT "ff"  ⊂ IF THISFONT ≤ 4 THEN "≥"  ELSE "fαf" ⊃;
.AT "fi"  ⊂ IF THISFONT ≤ 4 THEN "α≡" ELSE "fαi" ⊃;
.AT "fl"  ⊂ IF THISFONT ≤ 4 THEN "∨"  ELSE "fαl" ⊃;
.PORTION MACROS
.SELECT 1
.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
.MACRO BB ⊂ BEGIN NOFILL SELECT 3 INDENT 0 GROUP ⊃
.MACRO E ⊂ APART END ⊃
.MACRO D ⊂ ONCE PREFACE 100 MILLS ⊃
.MACRO BBB ⊂ BEGIN  SINGLE SPACE; PREFACE 1; NOFILL GROUP ⊃
.MACRO BB2 ⊂ BEGIN  SINGLE SPACE; FILL ⊃
.MACRO B4 ⊂ BEGIN NOFILL INDENT 0  SELECT 2  WIDEN 6,8  PREFACE 10 MILLS ⊃
.MACRO B5 ⊂ BEGIN FILL INDENT 0  SELECT 7  PREFACE 5 MILLS  SPACING 0 MILLS ⊃
.MACRO FAD ⊂FILL ADJUST COMPACT DOUBLE SPACE; PREFACE 2 ⊃
.FAD

.MACRO NSECP(A)  ⊂   SSECNUM←0
.SECNUM←SECNUM+1 
.SECTION←"A"
.SKIP TO COLUMN 1
.TURN ON "{∞→"   
.SEND CONTENTS ⊂
@1{SECNUM}. A⊗* ∞.→ {PAGE}
.⊃
.TURN OFF "{∞→"   
.ONCE CENTER TURN ON "{}"
@5↓_{SECNUM}. A_↓⊗*  
.  ⊃


.MACRO ASEC(A)  ⊂  SSECNUM←0
.SECTION←"A"
.SKIP TO COLUMN 1
.TURN ON "{∞→"   
.SEND CONTENTS ⊂
@1 A⊗*
.⊃
.TURN OFF "{∞→"   
.ONCE CENTER TURN ON "{}"
@5↓_A_↓⊗*  
.  ⊃


.MACRO NSEC(A)  ⊂  
.SSECNUM←0
.SECNUM←SECNUM+1 
.TURN ON "{∞→"   
.SEND CONTENTS ⊂
@1{SECNUM}. A⊗* ∞.→ {PAGE}
.⊃
.TURN OFF "{∞→"   
.SECTION←"A"
.GROUP SKIP 3
.ONCE CENTER TURN ON "{}"
@5↓_{SECNUM}. A_↓⊗*  
.  ⊃


.MACRO SSEC(A)  ⊂  TURN ON "{∞→"   
.SSECNUM←SSECNUM+1
.SSSECNUM←0
.SEND CONTENTS ⊂
@7               A⊗* ∞.→ {PAGE}
.⊃
.TURN OFF "{∞→"   
.ONCE INDENT 6 TURN ON "{}"
@2↓_{SECNUM}.{SSECNUM}. A_↓⊗*  
. ⊃

.MACRO ASSEC(A)  ⊂  TURN ON "{∞→"   
.SEND CONTENTS ⊂
@7               A⊗*
.⊃
.TURN OFF "{∞→"   
.ONCE INDENT 6 TURN ON "{}"
@2↓_A_↓⊗*  
. ⊃

.MACRO SSSEC(A)  ⊂  TURN ON "{∞→"   
.SSSECNUM←SSSECNUM+1
.TURN OFF "{∞→"   
.ONCE INDENT 1 TURN ON "{}"
@2↓_{SECNUM}.{SSECNUM}.{SSSECNUM}. A_↓⊗*  
. ⊃

.SECNUM←0
.PAGE←0
.NEXT PAGE
.TURN OFF "{"
.INDENT 0
.SELECT 1
.INSERT CONTENTS
.PAGE←0
.PORTION THESIS
.TURN OFF "{∞→}"   
.EVERY FOOTING(⊗7{DATE},Section:  {SECTION},page {PAGE}⊗*)
.EVERY HEADING(⊗7Douglas B. Lenat,,Interacting Knowledge Modules⊗*)
.PAGE←1
.ASEC(Summary)
.NARROW 6,8

Encouraged by the success of living creatures, we extract a few key features
of organisms and use them as constraints in designing 
a knowledge-based computer program.
In particular, our system will consist of discrete knowledge modules, each having
a standard anatomy, whose primary activities are (i) observing the environment and
recognizing self-relevance, (ii) posing demands on each other, (iii) satisfying
each other's needs, (iv) generating new modules which inherit family traits.

The development of these ideas, and a study of their implications, occupies
the first part of this paper. Next comes a concrete realization: a system
of 100 modules, programmed in LISP, which managed to synthesize three nontrivial
LISP programs. 
Each module corresponded to an expert, a specialist in one tiny aspect of
programming, psychology, management, or communication.
The most demanding constraint was that the community of modules be able to reproduce
a specific discussion which occurred among human experts given the same programming
task.
The problems encountered suggest a new domain; we turn from
automatic programming to fundamental mathematics research. The math system
is not implemented yet, but its design details and its expected behavior are
described in the third and final section of the paper.

.PAGE←1

.NSECP(Theory)

.SSEC(Origins of the Constraints)

Despite the awesome physical forces affecting Earth (weather, gravitation,... ),
it is ⊗4biological⊗* entities
who dominate our planet.  Much of science and philosophy are aimed at 
observing and explaining this mystery.  One approach to Artificial Intelligence
is to assume that Man "works," then try to model his attributes in a mechanical
device (or, equivalently, in a computer simulation). This paper describes one
such project. We shall begin by extracting the most obvious characteristics of
living organisms, especially of Man, and then design a program which incorporates
them.

Perhaps the most obvious distinction between, e.g., Weather and Animals, is that
of ⊗4discreteness⊗*. Yet besides  having distinguishable boundaries, each
species has a specific ⊗4anatomy⊗*. That is, each such creature is alike in
many important functional, physiological, structural, and psychological respects.
More than uniformity is required; the grains of sand in a desert fit our description
as it now stands. 
⊗4Individual abilities⊗* must be recognized; despite their similarity,
each member of a species is slightly different in his perception of
features of his environment, in his responses to those features, 
in his drives, and in his
capabilites. In many species, including humans, this has been carried to the extreme
of ⊗4professions.⊗* Each individual has an occupation, a specialty. A collection
of diversified experts is more viable than a similar collection of generalists.

So we limit our attention to  a community of discrete entities, 
sensitive to the world around them, each with his own distinct
expertise, yet all anatomically and psychologically similar.
How do they ⊗4interact⊗* in a meaningful, productive manner? 
Biology would lead us to hypothesize ⊗4competition⊗*, but 
perhaps the key is
⊗4cooperation.⊗*  Specialization is of advantage only if each specialist is willing
to use his talent to serve the entire community. In part this may be instinctive,
but much of Man's supremacy stems from learning to cooperate. The institutions
of the law, education, and government universally reflect (distortions of) this
ideal. 
Advancement ⊗4within⊗* a society may be by competition, 
but advancement ⊗4of⊗* a society
necessitiates synergy.
But how do people help each other; what is the "mechanism"? 
Perhaps it lies in ⊗4communication⊗*. This has three aspects: 
(i) broadcasting your own needs to the specialists who might help you, or to the
entire community; (ii) recognizing
when you are relevant to satisfying someone else's specific need; (iii) satisfying
that need, often by posing new sub-requests to the community.

Besides communication, another constructive process of living 
entities is ⊗4reproduction.⊗*
The organisms combine, usually in small groups, and produce a new, similar being.
Heredity ensures that he will be somewhat similar to his parents, yet not identical.
The father teaches the son his trade; perhaps the offspring becomes even more of
a specialist in that field; perhaps he becomes more versatile by integrating
lessons learned from several of his ancestors.
We shall therefore assume that our entities can ⊗4reproduce and teach their 
progeny⊗*.

These characteristics are now ⊗4postulated⊗* as constraints on the computer
simulation we wish to construct. The program will be made up of discrete modules,
which we shall call BEINGs, each possessing a clump of specialized knowledge.
Each BEING shall have the same internal structure, can respond to the same kinds
of questions (though with different answers in each case). The only things that
a BEING can do are: broadcast a plea for assistance, recognize his own ability to
help in a certain situation, provide the needed answer in such cases, combine
with  0,1, or 2 other BEINGs to produce a new BEING, and teach that offspring
some of what it knows.

The reader may protest that much has been ignored: primitive drives, 
instincts, emotions,
aesthetics, ethics,...  Some of these will be dealt with in Section 3, when we
discuss design issues for a system which can make simple mathematical discoveries.
Such a system must have a sense of aesthetic beauty, harmony, innate interestingness,
as well as a sense of intuition, instinct.
It is not felt that the complexity of human emotions is 
prerequisite to intelligence;
BEINGs need not simulate emotions.  
No case shall be argued in favor of these
prejudices; rather, we shall test them, observing what happens
in a system which assumes them. This is the subject of Section 2. Before that
discussion, let us formally define some of our terms.


A ⊗4system⊗* of BEINGs, also called a ⊗4pool⊗*,
is a collection of knowledge modules, plus
auxilliary support functions (like "Pattern-match", "Sort"). A
⊗4BEING⊗* is nothing more than a collection of about thirty parts.
Each ⊗4part⊗* of BEING B is an ordered pair ⊗2(q,a)⊗*, where
⊗2↓_q_↓⊗* is an abbreviated name of a question, and ⊗2↓_a_↓⊗* is a
program which can be run to provide B's answer to ⊗2↓_q_↓⊗*. In the
course of executing ⊗2↓_a_↓⊗*, new questions may be raised, new
BEINGs may be created, parts of existing BEINGs may be changed, and
messages (hopefully including the desired answer) may be passed. 

Once again: the concept of a pool of BEINGs is that many specialized 
entities coexist, each
having a complex structure, but that structure does not vary from entity to entity.
This idea has analogues in many fields: transactional analysis in
psychology, anatomy in medicine, modular design in architechture.

It seems that ⊗2Q = {q}⊗* might need to be immense, to cover all the kinds of
queries any expert might ever want to put to another expert. In fact,
in order to make ||⊗2Q⊗*|| manageably small, it is necessary to restrict the
task domain of the BEINGs system. For example, a set Q↓c↓f of
30 parts can be found which suffice to discuss concept formation, and a
set Q↓[math] of 30 which suffice to discuss mathematical research, but those two
sets are almost disjoint.

.SSEC(How to Build Such a System)

How can we test out this idea? We must build a pool of BEINGs, a modular program
which will interact with a human user and 
do some specific task (like write a certain computer program, or propose
some specific mathematical conjecture and then find a proof for it).
Recasting the idea into operational terms, we arrive at this procedure for
constructing a pool of BEINGs: 

.BEGIN INDENT 0,4,0

(1) Study the task which the pool is to do. See
what kinds of questions are asked by (simulated) experts, as they cooperate to
carry out that task.

(2) Distill this into
a core of simple questions, ⊗2Q⊗*,
in such a way that each inter-expert question or transfer
of control can be rephrased in terms of some ⊗2↓_q_↓ ε Q⊗*.
The size of ⊗2Q⊗* is very important.
If Q is too large, addition of new
BEINGs will demand either great effort or great intelligence (an example of a
system like this is ACTORS↑1). If Q is too small, all the non-uniformity is simply
pushed down into the values of one or two general 
catchall questions (all first-order
logical languages do this). 

(3) List all the BEINGs who will be
present in the pool, and fill in their parts. 
The time and effort required to fill in a new BEING is  ⊗4independent⊗* of
the number of BEINGs already in the pool, because BEINGs can communicate
via nondeterministic goal-directed  mechanisms, and do 
not have to know the names of the BEINGs
who will answer their queries. 

(4) The human user interacts with the completed
BEING community, until the desired task is complete.

.END

In the next section, we apply this recipe to the task ⊗4"Write a concept formation
program in LISP, similar to the one described by Winston↑2".⊗*
The problems encountered will guide us to find a new domain (in Section 3) 
and change the formal
requirement that each BEING's set of questions be identical.

.NSECP(Application to Automatic Programming)

The system's task domain is chosen to be Automatic Programming; in particular,
we want a BEINGs system which can interact with a human user and synthesize a
concept formation↑3 program.  
By ⊗4Automatic Programming,⊗* we mean this interactive, nonformal process whereby
a human ⊗4user⊗* specifies a desired program to a ⊗4system⊗*, in a tiny subset of
some natural language, after which the system and user discuss details about the
task, until the desired program, called the
⊗4Target Program⊗*,
is finally synthesized.↑4
Any BEINGs which contain knowledge about concept formation will be called 
⊗4task-specific⊗*; those possessing program-writing knowledge are called
⊗4domain-specific⊗*; the most general BEINGs are ⊗4domain-independent⊗*.


.SSEC(Analogy: Cooperating Human Experts)

We now carry out the four-step procedure outlined
near the end of the last section.
The first step is to examine a community of expert organisms performing the 
program-writing task.
Let us imagine a room filled with humans from a variety of professions:
scientific programmers, psychologists, system hackers, engineers, troubleshooters,
logical theorists, managers, etc. There is one distinguished member: we may consider
him to be the director, sponsor, or ultimate User of the final product.
The user is the one who initially specifies what is wanted, who makes policy decisions,
and who is rarely called on by the other experts unless they have to.
The experts cooperate by asking each other questions, helping answer whatever they
can (and noticing when they might be able to assist), etc. Some of them can write
or modify parts of the partially-synthesized target program; ⊗4all⊗* of them can direct
programmers to do specific encodings.

A hypothetical dialogue was simulated, in which the concept formation program
was discussed and synthesized. This eventually called for 80 different experts,
asking about 10,000 questions altogether, 
all of which fell nicely into 29 categories
of questions. We constructed a BEING to model each particular human expert.

So our experimental system, called PUP6, should consist of a community of 80
BEINGs (and several minor utility functions). Each BEING should have 29 parts.
For each part of each BEING,
its ⊗2↓_q_↓⊗* subpart is simply a LISP identifier, an atom; the
⊗2↓_a_↓⊗* subpart is a LISP program, ranging from 1 to 60 lines in
length. 

.TURN OFF "{}"

The concept of anatomy is realized by constraining that each BEING in the PUP6
system have the same set ⊗2Q = {q↓1,...,q↓2↓9}⊗* of questions which it can answer.
Of course the values ⊗2↓_a_↓⊗* are different from individual to
individual.  For example, each BEING must have an EFFECTS part, that
is, a part whose question is abbreviated "⊗4EFFECTS⊗*". This part really answers
⊗4"What final effects can you produce; can you acheive this particular
goal...?"⊗*  The value filled in for the EFFECTS part of a BEING B is simply
a set of ⊗4<situation>/<action>⊗* productions: if the desired effect matches
⊗4<situation>⊗*, then it can be achieved by B, by executing the program ⊗4<action>⊗*.

Analyzing the simulated experts' discussion, there seems to be a single dominant
scenario for creation of new code. 
They work together to simulate the target concept formation program as it should
run.
When the concept formation program has to carry
out some task X, some expert will recognize his relevance. He will then carry out
X himself, introspect, extract the particular knowledge he is using to do X, and
tell a programmer exactly how he is doing X.↑5  The programmer then oversees the
encoding of this and the merging into the already-synthesized pieces of code.

In PUP6, new BEINGs are created analogously.
The typical act of BEING creation is when a single, general BEING, say
B, recognizes that he can do the desired target task, but also knows that
he is too general and inefficient to be duplicated precisely inside the
target program. Then B 
introspects, and, together with a programmer-BEING, assembles a
new, specialized, streamlined version of
itself, B', which can do the required task but not much else.
Other BEINGs  try to fill in or extend all the parts of B', so B' can answer
any of the 29 possible questions ⊗2Q⊗*.

The process of filling in all 29 parts of all 80 BEINGs was fairly routine. For
part p of BEING B, we simply looked through the simulated dialogue, collected all
the instances in which expert B answered a question in category p, then wrote a small
collection of facts and procedures which (i) embodied the knowledge that seemed to 
be required to produce these responses, (ii) ensured that in each of these situations,
the response given would be the same as the one in the dialogue. The first point
ensures we are not "cheating", the second point guarantees that the whole dialogue
can be reproduced by the BEINGs system, if the human user of PUP6 
makes exactly the same
requests, comments, and replies as the hypothetical user in the dialgoue.

.SSEC(Details of the Experimental System)

.ONCE TURN ON "[]"
Because of its genesis from a particular protocol dialogue↑6, it is not surprising
that the PUP6 system actually did manage to synthesize the target program. We shall
refer to that concept formation program↑2 as CF. By adding a few more BEINGs to the
system, the user was able to get PUP6 to write a grammatical inference program
(GI) and a simple property-list maintenance program (PL). Despite these promising
results, dialogue flexibility problems detracted greatly from PUP6.
Below are some specifics on that system; for a more detailed treatment, see ↑[4,7].

.SINGLE SPACE  PREFACE 1

.SSSEC(The BEINGs in PUP6)

We now summarize each BEING present in PUP6. After its name is its length
(in LISP cells), the number of BEING parts which were necessary to fill in for
that BEING, and a brief English description.
First we present those BEINGS used to write CF, then  the ones we
had to add to the system to get PUP6 to write GI and  PL. Among the
first group, we further subdivide it into (a) high-level
task-specific (concept formation), (b) low-level task-specific, (c) domain-specific
(programming),
(d) high-level  domain-independent, (e)
low-level  domain-independent, and (f) miscellaneous.
The number of
additional BEINGs to write GI and PL
is so small we don't subdivide their descriptions.

.BEGIN SELECT 6 NOFILL WIDEN 6,8


⊗1The knowledge necessary to write a concept formation program⊗*

	⊗1A. High-level, task-specific knowledge⊗*     How to do concept formation.

Psychologist. 582 cells. 18 parts. Eleven decisions to make about type of concept formation desired.
Classificatory-Concept-Formation. 37. 6. Partition a domain, in an interactive "guessing" manner.
Comparative-Concept-Formation. 45. 6. As above, then partially order the equivalence classes of the partition.
Metrical-Concept-Formation. 22. 4. As above, then induce a metric on the partial ordering of the classes.
Partition-a-Domain. 286. 16. In a guessing, interactive manner. 3 decisions about the flavor of the division.
Partition-by-take-element-get-class. 67. 9. Read in an ele, guess its name, check, update structures.
Partition-by-take-class-get-element. 40. 7. Read in concept name, guess its eles, check, update.
Partition-by-take-class-and-element. 64. 9. Read both scene and name, add to existing partition.

	⊗1B. Low-level, task-specific knowledge⊗*     Not useful in all pgm-writing.

Recognize-contradiction. 226 cells. 11 parts. Notices phrases involving incompatibility. Three flavors.
Probability ≡ 0 Contradiction. 122. 10. Something should not occur but it does.
Probability ≡ 1 Contradiction. 106. 10. Something should occur but it doesn't.
Probability >0 AND <1 Contradiction. 118. 10. No restriction on x's appearance, so never a contradiction.
Scene. 48. 6. A data structure: objects, name, static relations, dynamic relations between objects.

	⊗1C. Domain-dependent knowledge⊗*  	  How to write programs.

Program-Manager. 631 cells. 17 parts. Doublecheck. Initialize, loop, finalize. Loop around following 4 B's:
Fill-In-undefined-Section. 463. 14. Choose piece to encode, try; if fail, decide why and try to fix.
Clarify-Improbable-Situation. 2102. 13. Concentrate on some warning about quirk in existing code.
Support-and-Dump. 445. 11. After Program-manager finishes, dump new BEINGs and needed old ones onto file.
Make-Encodable. 162. 11. Last resort; replace B by an alternative or a generalization.
Encode. 1018. 12. Just a bookkeeper. Gather info, build schema, worry about args, call Make-Being.
Determine-Arg-Value. Locate where in the target pgm a given BEING will be called.
Flow-Preceded. Search through the target code and notice references to x.
Get-Data-Structure. 780. 13. Select type of repr., set it up, warn about modifications.
Select-Structure-Type. Bits of wisdom, e.g. "several weakly-interacting pieces indicate property list"
Element. 59. 8. All we know is that it is a member of a data structure.
Modify-Structure. 158. 12. Given ele., find which data structure it belongs to, insert or delete it.
Get-Hold-Of-the-Hard-Way. 301. 11. Guess (by Compute, Search, or Generate-and-test), then check.
Take-Hold-Of-the-Easy-Way. 505. 10. Via assignment to existing variable, or via reading it in.
Complex-Alteration. 498. 10. Initializing assignments, then modify substructures of given structure.
Conditional-Deletion. 878. 12. Decide what is to be deleted from where, and under what conditions.
Conditional-Insertion. 1244. 11. Decide what is to be inserted where, and under what conditions.
Some-Part-Of. 220. 11. Get simple destructive function, by inferring from examples or simple translation.
Joining-Function. 223. 13. Simple way of condensing results. Typically And, Or, Plus, Maximum.

	⊗1D. High-level, domain-independent knowledge⊗*    Useful in any BEINGs system.

Serve-the-User. 204 cells. 15 parts. Obtain info. until some of it is "executable", then carry it out.
Obtain-Usable-Information (Info-Obtainer). 199. 13. Choose from 4 ways to get new facts.
Use-Information. 148. 11. Pick best piece of info, try to execute it, repeat until successful.
Get-New-Info. 192. 15. Decide what is needed, make it specific, ask user, translate.
Extract-Relevant-Subset. 203. 13. Constrain what is being looked at; focus on relevant subpart.
Analyze-Implications. 276. 14. Locate affected area, predict affects, evaluate desirability.
Study-Type. 224. 11. If x is too general, ask x how to specialize x in this case. 
Make-New-Being. 461. 11. Simply accept info. about parts of new B, create one with those parts.
Search. 375. 13. Test each member of space; worry about termination criteria and behavior.
Generate-and-Test, and Compute, were never actually needed, and were therefore never coded.
Foreach. 938. 12. The iteration BEING. Minor decisions similar to those in Search.
Test. 269. 8. Threshhold of acceptability; decide whether result is ratio, ordinal, or just nominal.
Compare. 982. 12. Often by comparing subparts of the args pairwise, or by simple Joining function.

.XGENLINES←XGENLINES-1
	⊗1E. Low-level domain-independent knowledge⊗*      Useful in any BEINGs system.

Get-Name. 592 cells. 14 parts. Ask for plausible names for the new, specialized BEING; have user choose.
Propose-Plausible-Names. 356. 15. Apply: Initials, Mainwords, Firstfew, & compos'ns. of these to task descrip.
Is-Of-Type. 143. 11. Predicate indicating containment. Too general to be powerful.
Choose-From. 312. 11. Select the best BEING and apply it; repeat until one succeeds.
Satisfy. 311. 18. Handles pattern-directed invocation. Broadcast plea, then Choose-from responders.
Messenger. 236. 15. Make user aware of x by printing x out (if not just done recently).
Translate. 328. 17. Broadcast to Iden parts of all BEINGs, let the best responder take over.
Reinvestigate-Decision. 200. 13. Try to keep deferring a particular decision.
Defer-Decision. 289. 15. See When next it matters. If you can defer it, fine; if not, resolve it.
When-Next. 244. 12. Manipulate the decision, to find the situation where it matters.
Utilize. 328. 12. Apply knowledge rules until success. Called by When-Next.
Resolve-Decision. 184. 13. Trivial inference; then resort to asking the user.
Ask-User-About. 195. 12. Type out details of the decision, then interpret user's answer.
Better. 405. 13. Decide which of given 2 BEINGs should gain control.
Handling of User Interrupts. Done by utility functions. User decides frequency of interrupts.

	⊗1F. Miscellaneous⊗*

Programming Knowledge stored in variables. How to defer and how to resolve these types of decisions:
	Adaptation, Known-Affects, Alternatives, Boolean, Define, Dichotomy, Predicate, Someof, Subsetof.
	How to terminate an AND loop, set up a Nested List, set up Property List.
Natural Language Translation. Involves mmny simple BEINGs, besides Translate.
	Recognize-Args, Recognize-C*R, Recognize-Conditional, Recognize-Conjunction,
	Recognize-Equality, Recognize-Function-Returns, Recognize-Inclusion, Recognize-Literals,
	Recognize-Number, Recognize-Set-Relations, Recognize-Some Member, Add-Definition, 
	Adjective-Handler, Repeatedly, Recognize-Contradiction. 
	Also, there are several functions related to translation: e.g., Ungerundify, Plural, Opposite.
Long-name-demon.↑8 Watch out for unwieldy, long names, ask user for nickname.
Structure-inducing-demon. Replace testing for special subtype by physical structuring along that dimension.

⊗1The increment of knowledge necessary to write GI⊗*

Apply-Rule. 118 cells. 10 parts. Try to apply given rule to given string. Sometimes: repeat till no change.
Constrain. 223. 14. Is it meaningful that x could grow without limit?  Possible restrictions.
Grammatical-Inference. 219. 12. High-level, domain-specific. Infer from example strings. "Test" means "parse"
Infer-Multi-Class-grammars. 88. 10. Infer type of grammar as well as grammar itself.
Infer-Fixed-Class-grammars. 131. 10. Type of grammar to be inferred is known beforehand.
Infer-Phrase-Structure-grammars. 143. 14. No rule constraints in type 0 grammar.
Infer-Context-Sensitive-grammars. 147. 13. Pruning heuristic: Right side of each rule is ≥ left side.
Infer-Context-Free-grammars. 148. 13. Pruning heur.: Left side is single nonterminal. Normal forms.
Infer-Regular-grammars. 155. 13. Pruning heur.: Unit on left, pair of units (term,nonterm) on right.
Major-Modify-Structure. 35. 6. Either standard modify, modify-until, or modify-some.
Modify-Some. 263. 9. Determine set S and predicate P now. At runtime, modify x iff P(x).
Modify-Until. 116. 9. Composition of Repeatedly with Modify-Structure.
Parse. 1223. 12. Invert each propsed rule and compose the results. Five decisions to make.
Parse Backward. 492. 11. Invert rules, apply to target string, repeat until acheive starting string.
Parse Forward. 488. 11. Use the rules to get from start to goal string.
String. 98. 12. Data structure: name, list of letters, set of comments. 

⊗1The increment of knowledge necessary to write PL⊗*

Examine-Structure. 146 cells. 11 parts. Select matching function, use it to compare subparts of struc.
Pattern-Match. 435. 12. Includes knowledge about how to write specialized matchers.

.END
.SINGLE SPACE PREFACE 1
.SSSEC(The parts of a BEING)

A set of 29 ubiquitous questions were chosen, representing everything one
expert might want to ask another. 
At least, they naturally encompass those questions which were asked during the
simulated meeting, hence should be sufficient for generating CF.
⊗2Q↓c↓f⊗*, this
universal set of BEING parts, is listed in the box below.
One potential flaw of a universal set  of parts is that  each BEING might really
only want to answer a few of the questions; many of them should not be asked of
him. In fact, this superfluity was found to exist. It was not tolerable, and led
to the Families concept, which will be introduced in section 3.
Each part was needed by only about a third of all the BEINGs in the PUP6 system,
in order for PUP6 to be able to generate CF properly.
The percentage of the BEINGs in PUP6
which actually needed each part is also noted below.
.XGENLINES←XGENLINES-3
.BEGIN NOFILL GROUP  PREFACE 0 MILLS  WIDEN 0,3  TURN ON "→∞"  SELECT 8
.ONCE TURN OFF "α"
⊂∞α→⊃
.SELECT 6
⊗8~⊗*						⊗2↓_BEING Parts_↓⊗* →⊗8~⊗*
⊗8~⊗*⊗2WHAT⊗* 82%  A brief summary of the global purpose, a template for an English phrase.→⊗8~⊗*
⊗8~⊗*⊗2WHY⊗* 77%  A justification of the BEING's existence, partly filled in by the BEING who called it.→⊗8~⊗*
⊗8~⊗*⊗2HOW⊗* 72%  A summary of the methods the BEING intends to employ. Global strategies.→⊗8~⊗*
⊗8~⊗*⊗2IDEN⊗* 54%  How this BEING is referenced in English phrases. Implemented as productions.→⊗8~⊗*
⊗8~⊗*⊗2WHEN⊗* 19%  Why this BEING should be given control now. The sum of weighted factors.→⊗8~⊗*
⊗8~⊗*⊗2ARGS⊗* 63%  Number of arguments; which are optional; names of any local variables.→⊗8~⊗*
⊗8~⊗*⊗2ARG-CHECK⊗* 81%  Predicates which examine each argument for suitability.→⊗8~⊗*
⊗8~⊗*⊗2EVAL-ARGS⊗*  4%  Which arguments are to be evaluated, and which quoted.→⊗8~⊗*
⊗8~⊗*⊗2REQUISITES⊗* 10%  If this BEING is actually chosen, what must be made true prior to (pre)→⊗8~⊗*
⊗8~⊗*		during (co), and after (post) execution.  Work to make these true (unlike ARG-CHECK).→⊗8~⊗*
⊗8~⊗*⊗2DEMONS⊗* 7%  Set of demons to be kept active while the BEING is in control.→⊗8~⊗*
⊗8~⊗*⊗2INHIBIT-DEMONS⊗*  5%  A lock/unlock mechanism, useful when handling demonic interrupts.→⊗8~⊗*
⊗8~⊗*⊗2EFFECTS⊗* 27%  What will probably be true after this BEING is through. What it achieves.→⊗8~⊗*
⊗8~⊗*⊗2RESULTS⊗* 15%  How many values this returns. What domain each is in. Side effects.→⊗8~⊗*
⊗8~⊗*⊗2META-CODE⊗* 70%  The body of the executable code, but with uninstantiated subparts.→⊗8~⊗*
⊗8~⊗*⊗2COMMENTS⊗* 16%  Hints for filling in undefined sections of other BEING parts.→⊗8~⊗*
⊗8~⊗*⊗2STRUCTURE⊗* 4% Viewing this BEING as a data structure, the operations doable to it.→⊗8~⊗*
⊗8~⊗*⊗2AFFECTS⊗* 14%  Other BEINGs which might be called by this BEING, and why.→⊗8~⊗*
⊗8~⊗*⊗2COMPLEXITY⊗* 92%  A vector of utility measures, including probable ease of calling,→⊗8~⊗*
⊗8~⊗*		of success, of (calling)* itself, time/space cost, efficiency of its output results.→⊗8~⊗*
⊗8~⊗*⊗2GENERALIZATIONS⊗* 27%  Some other BEINGs, encompassing this one.→⊗8~⊗*
⊗8~⊗*⊗2ALTERNATIVES⊗* 16%  Some equivalent BEINGs (to try if this one fails).→⊗8~⊗*
⊗8~⊗*⊗2SPECIALIZATIONS⊗* 40%  How to write a streamlined, special-case version of this BEING.→⊗8~⊗*
⊗8~⊗*⊗2ENCODABLE⊗* 9%  How to order the evaluation of the other parts for self-streamlining.→⊗8~⊗*
.SELECT 8
.ONCE TURN OFF "α"
%∞α→$
.TURN OFF "∞→"
.END
.XGENLINES←XGENLINES-3
Each of the 100 BEINGs ultimately present in PUP6 should have
had a value for each part (in reality, only 40% were filled in; only 30% were
actually necessary to generate CF). 

The set of parts breaks into three rough categories: those parts which
are useful in deciding which BEING gets control, those useful primarily in
answering the user's questions and keeping him oriented, and those useful when
the BEING gains control.

.SSSEC(Gaining Control)

At the humans' meeting, only one expert spoke at a time; in the BEINGs
community, only one BEING has control at any given moment. He uses his
parts to do things (ask, create, modify), and yields control either
voluntarily or through interruption. 

In slightly more procedural terms, the scenario is as follows. Some part of
a BEING B senses B's relevance (often the IDEN or EFFECTS parts, which are
united with all such parts to form a large production system). If more than
one BEING wants control at any time, a special BEING, CHOOSER, seizes
control momentarily. He asks each competing 
BEING to evaluate its WHEN part, to see
how seriously it needs to go immediately. If some BEINGs are still tied for
first place, he asks them to evaluate their COMPLEXITY parts, to see which is
the simplest. If any ⊗4still⊗* tie for top, one is randomly chosen. In any
case, the winner is then passed control. Once in control, BEING B arranges
some of its parts in some order and evaluates them. For example, B's ARGS
part might be first; if it asks for some arguments which no BEING has 
supplied, then the whole BEING might decide to fail. Some  parts, when evaluated,
might create a new BEING, might ask questions which require this whole process
to repeat recursively, etc. 
This "asking" really means broadcasting a request to one or two parts of
every BEING; for example "Is there a known fast way of gronking toves?" would
be asked as a search for a BEING whose COMPLEXITY indicated speed, and whose
EFFECTS part contained a production with a template matching "gronking toves".
A list of the responders would be returned to B.
(Incidentally, GERUND would recognize this, but later give up when no one
could recognize "gronk toves".)
B might then pose some
new questions directly to these responders, might turn control over to them directly,
etc. One way or another,
B eventually relinquishes control. If it had no direct successor in mind,
all the BEINGs in the system are asked if they want to take over.  
There will always be ⊗4some⊗* BEING who will take over;
the general management
types of BEINGs are always able  -- but reluctant  -- to do so. 

How does each BEING decide which parts to evaluate, and in which order,
once it gains control?
The answer might seem to be difficult or tedious for whoever writes
BEINGs, since it might vary from BEING to BEING. In fact,
it doesn't!
The commitment to a universal set of BEING parts is inefficient in some ways
(each BEING ⊗4needed⊗* only a third of all the parts) but allows for some
simplifications right here. 
What parts should be evaluated, and in what order, when a 
BEING gains control? This decision depends primarily on the ⊗4types⊗* {⊗2q⊗*} of 
parts present in the BEING, not on their ⊗4values⊗*
{⊗2a⊗*}.
But every BEING has the same
anatomy, ⊗2Q⊗*, so one single algorithm can assemble any BEING's 
parts into an executable
LISP function. Moreover, this assemby can be done when the system is first
loaded (or when a new BEING is first created), and need only be redone for a
BEING when the values of its parts change. Such changes are rare: experts are
not often open-minded. 
The parts useful here include
ARGS, DEMONS, META-CODE, COMMENTS, ARG-CHECK, and REQUISITES.

.SSSEC(Keeping the User Informed)

In the simulated dialogue, the user had no trouble
whatever understanding what the  experts asked him. In the actual
programmed PUP6 system, the human who was sitting at the teletype quite
⊗4rarely⊗* understood what was wanted by the BEINGs. He frequently had to
interrupt them and ask them questions about who was in control, why, what
he was trying to do, what had recently transpired, etc. These ideally can
be phrased as simple retrievals and EVALs of active BEINGs' parts.
The BEING parts
most often called for by the user are the simple one-line "orientation"
templates. These include WHAT, HOW, WHY, and AFFECTS.  Since BEINGs can only create
new BEINGs (not simple LISP functions),
the synthesized program, CF, was writen as a pool of BEINGs itself
(by PUP6, but not during the protocol). 
Although its question-answering ability is inferior to PUP6, the fact that CF
has ⊗4any⊗* such power was surprising to the author. In other words,
one can interrupt the synthesized program as it is running
and ask questions. Any BEING on the control stack will provide fully instantiated
answers to any of its 29 allowable queries (its parts); all other BEINGs will provide only
hypothetical answers. As an example, consider this actual excerpt of a human
using the CF program synthesized by PUP6.
"???" simply means "guess the name of the scene with these objects and relations".
CF types in boldface, the user in italics.

.B4

READY TO ACCEPT BRAND NEW SCENE:   ⊗4(??? (A B) (Block A) (Block B) (Supports A B))⊗*
NOT AN ARCH. NOT A TENT. MIGHT BE A HOUSE.  MY GUESS IS HOUSE.
WHAT IS IT REALLY?		   ⊗4Nothing⊗*
TRANSFER FROM MAY TO MUST-NOT SETS OF HOUSE: (BLOCK  B)
.END

Here is the ⊗4same⊗* excerpt, but with the user interrupting occasionally.
"⊗4U:⊗*"
signifies he has interrupted,
and "⊗4OK.⊗*" signifies he has told CF "⊗4OK, go back to work now.⊗*"

.EPAGE←PAGE
.B4

	⊗4U:  What are you doing?⊗*
CF:  Divide a domain into subdomains, using specialized version of PARTITION-DOMAIN.
  	⊗4How?⊗*
CF:  By building up the partition gradually, by adding one <scene, name> pair.    ⊗4OK.⊗*
.D
READY TO ACCEPT BRAND NEW SCENE:   ⊗4(??? (A B) (Block A) (Green B) (Supports A B))⊗*
.D
	⊗4U:  What are you doing?⊗*
CF:  Break OBJECTS piece off (??? (A B) (BLOCK A) (GREEN B) (SUPPORTS A B)) to examine.
	⊗4What code is the current BEING going to execute?⊗*
CF:  The meta-code of SOME-PART-OF↓1↓4 is (CADR arg1). Evals to (A B).    ⊗4OK.⊗*
.D
NOT AN ARCH.
	⊗4U:  Why?⊗*
CF: The ARCH MUST-NOT-relation (SUPPORTS A B) is contradicted in the SCENE.    ⊗4OK.⊗*
.D
NOT A TENT. MIGHT BE A HOUSE.  MY GUESS IS HOUSE.
WHAT IS IT REALLY?		   ⊗4U:  Why are you asking?⊗*
CF: CF cannot resolve it, and must at this time, so CF asks USER
	⊗4OK. What you wanted is:   Nothing⊗*
.D
	⊗4U:  What are you doing?⊗*
CF: Go through space of concept names, and make user aware of changes.
	⊗4What BEINGs might this affect?⊗*
CF: MESSAGE is possibly called; some version of TEST is possibly called.     ⊗4OK.⊗*
.D
TRANSFER FROM MAY TO MUST-NOT SETS OF HOUSE: (BLOCK  B)
	⊗4U:  Why?⊗*
CF: Change model of HOUSE until it contradicts the previous SCENE.	   ⊗4OK.⊗*

.END
.FAD
.SSEC(Results)

Three of the most significant questions for automatic programming systems operating
informally via dialogue are (i)
what kinds of things the user must tell the
system, 
(ii) how it manages to carry on that dialogue,
and (iii) what programs are synthesized.

.SSSEC(Character of the Dialogue between User and PUP6)

By lumping all the parts of the PUP6 system together conceptually, the
interaction is seen as a ⊗4dialogue⊗* between a human user and an automatic
programming system.  We present below the initial few lines of the actual
300-page long dialogue which resulted in CF being generated. This is shown as
the human user of PUP6 might see it; in the next section we describe how the
BEINGs actually interacted to manage this.

.BEGIN NOFILL  SELECT 8   PREFACE 0 MILLS  TURN ON "→∞"
.D1PAGE←PAGE

.ONCE TURN OFF "α"
⊂∞α→⊃
.SELECT 2
⊗8~⊗* PUP: I want any task.→⊗8~⊗*
⊗8~⊗* ⊗4USER: Write a program which does concept formation.⊗*→⊗8~⊗*
⊗8~⊗* PUP: I am about to write a program for ⊗6specialized CONCEPT-FORMATION⊗*.→⊗8~⊗*
⊗8~⊗* PUP: Give me a proper name for this program. (I suggest CF or CONCEPT)→⊗8~⊗*
⊗8~⊗* ⊗4USER: CF.⊗*→⊗8~⊗*
⊗8~⊗* PUP: I am temporarily replacing the task "⊗6specialized form of CONCEPT-FORMATION⊗*"→⊗8~⊗*
⊗8~⊗*		by "⊗6specialized form of PARTITION-A-DOMAIN⊗*".→⊗8~⊗*
⊗8~⊗* PUP: Must CF mimic different human subjects? (respond YES, NO, ?, or DETAILS)→⊗8~⊗*
⊗8~⊗* ⊗4USER: NO.⊗*→⊗8~⊗*
.SELECT 8
.ONCE TURN OFF "α"
%∞α→$
.END
From the above, one gets the true impression that the dialogue was fairly tedious:
choosing names and resolving design decisions ⊗4was⊗* 
the user's main role. There were,
in sum, about 300 such responses involved in generating CF. 13 crucial responses
were also necessary,
where the user supplies needed information that was not explicitly requested by
the BEINGs.
A few of these key lines are: ⊗4Write a program which does
concept formation; An "element of the domain of stimuli" is a static scene; The
guessing process is one of searching, not computing; Terminate the loop iff any
model feature is incompatible with the scene's features⊗*. In addition, the user
must check over each decision to transfer between data structures: he must
verify what gets transferred, when, and why. {There ought to be 
an Analogic-Inference BEING
which learns from the first couple such tedious constructions, and answers for
the user during the writing of the last several transfer functions.}

The translation mechanism is simply the IDEN parts of all the BEINGs. Each such
part contains a few productions, which are united with those of the other BEINGs
into one large production system. The left side of a production is a template
which is matched against the given phrase. The right side is a small program to
be executed in case the phrase is recognized. Generally, that program simply says
to translate some subphrase of the phrase, and then (probably) pass control
to the BEING which this is in the IDEN part of.
While not up to the "state of the art" in natural language processing, this is both
adequate and faithful to the spirit of distributing problems over 
all the BEINGs, by making them ⊗4parts⊗*, so it is each BEING's duty to know a
little about them.
The result of translation is to call on a certain BEING, giving him a certain mission.

Because of its genesis from a single "experts meeting" polylogue
(discussion among several individuals),
hereafter referred to as the ⊗4protocol⊗*,
the PUP6 pool of BEINGs was simply
not capable of widely varied dialogues with the user.  
Two assumptions implicit 
in using the simulated experts' discussion as a literal model
turned out to be serious: (i) the abilities of any
actual user of PUP6 must coincide with those of the user who was simulated in the
protocol, and (ii) the order of and wording of the actual user's 
comments must closely
adhere to those of the user in the protocol. Such difficulties must be overcome
in any system
designed for wide usership, but were considered ignorable in the specific
automatic code generation task at hand.

Also
as a result of this approach to system specification, each BEING had only those
parts specified which it actually would need in the ensuing dialogue.
Part of the difficulty with new dialogues stemmed from this minimal completion.
In the protocol, when a decision was made by experts,
the knowledge necessary to follow the
⊗4other⊗* alternative branch was not used, nor were such superfluous
facts supplied to the BEINGs in PUP6. Thus
the user of PUP6 must almost always resolve each choice the way the simulated
(protocol) user did.
It is felt that if all the parts of all the BEINGs had been faithfully filled
in, this problem would have subsided. Basically, the difficulty is one of
modelling all the possibly relevant knowledge an expert has, rather than
(as was done) just capturing enough of his knowledge to do a few given tasks.

While all the BEINGs' interactions were invisible to the user, the system still
swamped him with data about what was going on. For example,
most of the entities he was asked to name were never referressary to include a BEING which
simulated forgetfulness, to prevent, e.g., anaphora spanning minutes of real time.
Orienting the user was not solved satisfactorally. Pointers into
a graph of generated code were simulated, but often a user wished to refer to
a piece of code not by name or by pointing, but by some brief meaningful
(to him only!) phrase.

.SSSEC(How the BEINGs Interacted to Carry on that Dialogue)

.ONCE TURN ON "{}"
We now present a loosely-translated glimpse of how the BEINGs in PUP6 cooperated 
to produce the first few lines of dialogue (at the beginning of section 2.3.1,
on page {D1PAGE}).

.GROUP SKIP 2

.BEGIN FILL SPACING 0 MILLS PREFACE 20 MILLS WIDEN 6,8 INDENT 0,4,0  SELECT 1

SERVE-USER: Is there any executable task to perform? <No one responds.>
Do we have any information sitting around that might lead to one? <No response.>
Very well, we must ask the user what he wants us to do. Somebody do that.

ASK-USER-ABOUT: My IDEN part matches any expression of the form "Ask user ←←x",
so I can do what you want. What specifically is it that the user should type in?

SERVE-USER: Anything which can be executed, any task for the system.

ASK-USER-ABOUT: Fine. The user should get the prompt "I, PUP6, want any task."

MESSENGER: I can deliver that message. 
<Types out to the user "PUP: I want any task.">

USER: ⊗4Write a program which does concept formation.⊗*

SERVE-USER: Can anybody here figure out what to do, what the user's saying?

PGM-MANAGER: I can. He wants a computer program to be written. If somebody will
explain the task "concept formation" to me, I'll delegate it properly.

PSYCHOLOGIST: Permit me to assist you. I know all about concept formation...

PGM-MANAGER: Wait, let me tell the user that we'll be able to handle the job.

MESSENGER: Here, I can take that message. Go on with your work. <Types out
"PUP: I am about to write a program for ⊗6specialized  CONCEPT-FORMATION⊗*.">

PGM-MANAGER: My prerequisite says we need a name for this program. 
Somebody get one, please.

GET-NAME:  I recognize that request. Who can think up some suggestions?

PROPOSE-PLAUSIBLE-NAMES: How about "CONCEPT"? Maybe just "CF". 

GET-NAME: Let's ask the user to decide.

MESSENGER: <Types out "PUP: Give me a proper name for this program. (I suggest
CF or CONCEPT)">

⊗4USER: CF.⊗*

PGM-MANAGER: 
My META-CODE part says that there are four candidates,
one of whom must take over 
control now in an important way. Each of them always wants to do something different.
How can I decide?

CHOOSER: Give me their names and I'll choose the best one for you.

PGM-MANAGER: They are INFO-OBTAINER, INFO-USER, PGMMER, and ANALYST.

CHOOSER: You four experts each must justify to me why 
you should take control now.
.BEGIN INDENT 4,10,0

PGMMER: Well, I suppose I could set up some "empty" top-level function, er...

INFO-USER: Let me have the floor! I know what to do with the user's specification.

ANALYST: Marginal profits accruing from my working at this point in 
time do not warrant...

INFO-OBTAINER: We already have some unused information, so my WHEN value is low; I 
can wait.
.END

CHOOSER: Okay, INFO-USER, you seem to be the only  expert whose WHEN part indicates
any timeliness here.

INFO-USER: First thing is for PSYCHOLOGIST to tell us how to actually ⊗4do⊗*
concept formation.

PSYCHOLOGIST:
My SPECIALIZATIONS part indicates that
there are several decisions to be made, depending on what your independent
variables and your experimental setup are. For example, are we studying one 
individual, or must our program adapt to simulate many different subjects? Must
stimulus items be just classified, or classified and ordered, 
or classified and ordered and
metrized? Are the scenes left in view indefinitely, or just the current scene, or is
even that one just flashed before the subject for a limited time? May the subject
make written notes? 
Can he learn from positive instances of the concepts?
from negative instances?
Is there to be any positive transfer effect...?

DEFER: Hold on here; we can't swamp the user with lots of unnecessary questions.
Let's go through each one and see if it can wait.
Consider the  decision about the task being classificatory, comparative, or
metrical. What is the first situation in which we really use the result of that 
choice?

WHEN-NEXT: I can get you that answer. 
This involves a list of alternatives. Who knows about that?

ALTERNATIVES: I know a few tricks here. If all the alternative sequences
of activities have the same initial subsequence, then do that common
subsequence before making the decision.

WHEN-NEXT: Do all three activities begin with the same intial subsequence?

UTILIZE: In this case, all three begin by partitioning a domain of elements.

DEFER: Temporarily, replace the task CF by the task of partitioning a domain.
<This is soon typed out to the user.>
Now consider the decision about subject-specific behavior being required.

PSYCHOLOGIST: This involves periodically inputting a description of the human subject.

ENCODER: That would mean adjusting the algorithms based on a vector of parameters.

WHEN-NEXT: This would probably affect the entire code. 

DEFER: I can't defer this decision. Someone had better take care of it.

RESOLVE: Ask the user about it.

ASK-USER: Phrase this as a yes/no question. Explain each alternative to the user.

MESSENGER: That's my job.
<Types out "PUP: Must CF mimic different human subjects?">

⊗4USER: NO.⊗*

DEFER: The next decision... 

  
⊗4Eleven decisions are ultimately proposed by PSYCHOLOGIST, and all but one are deferred.⊗*

INFO-USER: I have no objections now if someone wants the floor.

PGM-MANAGER: Do any of the other three experts I mentioned earlier want
to speak now?

PGMMER: Yes. The top-level function CF can now be coded.

ENCODER: Give me the arguments and the body of the code, please.

PGMMER: There are no known arguments. The body is a call on ⊗4PARTITION-DOMAIN⊗*.

CODER: Okay. I will precede that with a call to an ⊗4INITIALIZE⊗* function,
and follow it
with a call to a ⊗4FINALIZE⊗* function, which are both defined as NIL for now.
Is ⊗4PARTITION-DOMAIN⊗* simple enough to be composed right now and filled in here?

MATHEMATICIAN: No way. While conceptually elegant in its simplicity, 
any realizate...

CODER: Uh, thanks. There. The function CF is defined as

.ONCE INDENT 6
⊗6(LAMBDA ( ) (INITIALIZE) (PARTITION-DOMAIN) (FINALIZE)).⊗*

ANALYST: Remind me to examine the initialization and finalization functions at the
end of our task. If either function is still null, it will be deleted.

WARNER: I have just put that note into the code for CF, as a comment.

PGMMER: Can someone advise me of what else to do to finish defining this function?

PGM-MANAGER: Each function should have a proper name. Show the user the names you
have picked, and let him choose other ones if he prefers.

MESSENGER: Okay...  The user agrees to all three names for the function calls.

INFO-USER: Somebody, please tell the group 
how to ⊗4do⊗* partitioning of a space of examples.
.END

Near the end of the protocol, the user is asked which of the three types of concept
formation CF is supposed to do. He responds "⊗4CLASSIFICATORY only⊗*", and the
BEINGs discover that they are finished. All the newly created code is dumped
out onto a fresh file.

.SSSEC(The Range of Programs Synthesized by PUP6)

The system, PUP6, did eventually synthesize CF, 
the target concept formation program.
PUP6 was 200 pages of INTERLISP↑9,  CF was 30 pages long (6 pages when
coded by hand during the protocod). This was generated in 60 cpu minutes
(compiled, PDP-10 TENEX). The dialogue consisted of 300K characters typed by
PUP6, and 4K by the user. It occupied 300 pages, and five hours of real time.

Despite the lack of dialogue flexibility,
it ⊗4was⊗* felt that
most of the BEINGs could be useful in generating other programs. For this
reason, two additional target programs were specified. They were 
synthesized with little change to PUP6, but only by someone familiar
with the system.

The second target program, GI, is a grammatical inference program, which accepts
strings labelled LEGAL, ILLEGAL, or ??. In the latter case, GI must guess the
legality. Internally, potential sets of rules are maintained. Of the original
pool, 46 out of 70 "general" and "programming domain-dependent"
BEINGs were used in synthesizing both targets.
Three of the existing 17 
"CF task-specific" BEINGs also were useful (those involving partitioning).
Four totally new BEINGs had to be added, related to formal grammars and rules.
Unfortunately, the addition of ⊗4any⊗* new BEINGs demands that the
user be acquainted with the format conventions of PUP6.
The GI program generated was 20 pages long; a hand-coded
version was one-fifth that size.

PL was the final target program attempted, a simple property list manipulator.
It repeatedly accepts requests from the user to insert, inspect, or delete
some record(s). Any unspecified fields are treated as don't-cares, so a simple
pattern-matcher had to be synthesized.
39 ⊗4non-task-specific⊗* BEINGs were used in synthesizing ⊗4all three⊗* targets, 
and no
⊗4task-specific⊗* BEINGs were common to synthesizing PL and any other program.
One general BEING and one task-specific BEING had to be ⊗4added⊗* to PUP6 to enable
PL's generation.

.ONCE TURN ON "{}"
As described earlier, the BEINGs generate other BEINGs, never plain
functions. This explains the huge increases in target code lengths
in the PUP6 versions compared to the versions produced by hand when
simulating the experts (who wrote the target programs as functions).
CF was a pool of 56 brand new BEINGs, GI 37, and PL 24. As
with PUP6, one can interrupt the synthesized programs as they are running
and ask questions. Any BEING on the control stack will provide fully instantiated
answers to any of its 29 allowable queries (its parts); all other BEINGs will provide only
hypothetical answers. Recall the excerpt from CF itself running, found on
page {EPAGE}.

Some of the difficulties stem from the nature of the task. In any long dialogue,
the user often forgets, changes his mind, errs, etc. A very sophisticated user
model would be necessary to accomodate this errorful process in a
non-debugging system. 
Without such abilities, the system itself may be led into error.
While most bugs ⊗4are⊗* avoidable by careful
record-keeping, it proved unrealistic to make no provision for debugging a
new thirty-page program. When a few errors did occur, PUP6 itself had
to be altered.  

.FAD
.SSEC(Conclusions)

Some of the problems encountered in PUP6 were due to incomplete
filling in of BEINGs, poor choice of ⊗2Q⊗*, absence of needed BEINGs
(like "DEBUG"), overly simple translation mechanisms, limited channels
for communication, the need for every BEING to conform to a single 
set Q of questions, the creation of a system designed to do just one particular
task. 

The performance of the BEINGs representation itself in PUP6 is mixed.
Two advantages were hoped for by using a uniform set of BEING parts.
Addition of new BEINGs to the pool was not easy (for untrained users)
but communication among
BEINGs ⊗4was⊗* easy (fast, natural). Two
advantages were hoped for by keeping the BEINGs highly structured.
The interactions (especially with the user) were
brittle, but
the complex tasks put to the pool ⊗4were⊗* successfully completed.

The crippling problems are seen to be with user-system communication,
not with the ideas dicussed in Section 1.
Sophisticated, bug-free programs ⊗4were⊗* generated, after hours of fairly high
level dialogue with an active user, after tens of thousands of messages passed
among the BEINGs.
Part of this success is attributed to distributing
the responsibility for writing code and for recognizing relevance, to a hundred
entities, rather than having a few central monitors worry about everything.
The standardization of parts made filling in the BEINGs' contents fairly painless.

All this suggests two possible continuations, both of which are underway here
at the Stanford AI Lab. One is to
rethink the communication problems,
and develop a new system for the
concept formation program synthesis task. The earliest programs by our group↑4
were efforts to ⊗4generate the target program somehow⊗*; 
this PUP6 research insisted on ⊗4getting the
target program by going through one "proper" sequence of reasoning steps⊗*; 
the group's proposed continuation wants ⊗4several
untrained users to  succeed by many different "proper" routes⊗*.

 
The other way of continuing
is to find a task where BEINGs are well-suited, where
the problems encountered in PUP6 won't recur. What ⊗4are⊗* BEINGs good for?
The idea of a fixed set of parts (which distinguishes them from ACTORs↑1) is
useful if the mass of knowledge is 
too huge for one individual to keep "on top" of.
It then should be organized in a
very uniform way (to simplify preparing it for storage), 
yet it must also be highly structured
(to speed up retrieval). In fact, BEINGs can 
be utilized within the usual solution to a
large problem: a group project. The members split apart after agreeing
on what the set of parts is to be. 

In selecting the continuation, the problems in this research should be isolated
from the staggering complexities of natural
language handling. For these reasons, we next consider
automated research in the field of elementary number theory, 
as a potential task domain.
BEINGs are big and slow, but valuable for organizing knowledge in ways 
meaningful to how it will be used. In 
the system described in the next section, BEINGs will be one
-- but not the only -- 
internal mechanism for representing and manipulating knowledge.

.NSECP(Application to Mathematics Research)

.SSEC(Correcting difficulties of the Automatic Programming system)

The most devastating criticism of BEINGs was that, in PUP6, each BEING wanted only
about 10 of the 29 possible parts filled in; that is, each BEING part was
really needed only by a third of all the BEINGs,
in order for PUP6 to synthesize the concept formation program successfully.
Analyzing this problem leads us
back to the cooperating experts analogy. There, we find the additional structural
level of ⊗4professions⊗*. Experts within a given profession can communicate
some specialized questions and answers which would be unintelligible to outsiders.
Of course, many of the questions are found in more than one profession; a few are
really universal.

By changing the domain of the BEINGs' activities to elementary mathematics↑1↑0, 
the natural communication problems 
mentioned in the last section
become manageable.  A small core of primitive constructions must be mastered,
but after that, 
it is the user's responsibility to define
any additional phrases. This is true
in "real" mathematical research, and makes translation fairly routine.
A second advantage of this task domain is that  there is not any one specific
task which the system is expected to achieve.
A ⊗4solution⊗* to this task would mean successfully
accounting for the ⊗4driving⊗* and the ⊗4pruning⊗* forces which
result in interesting
mathematical theories being developed. Success
could be measured in operational terms, by applying these forces to
various domains of mathematics, and comparing the results to what is
already known in those fields.

Let us consider, then, the task of doing mathematical research: defining 
potentially interesting mathematical systems, and developing theorems about
them. Each BEING will represent a conceptualization: either a mathematical
construction, an activity, a meta-concept, etc.  The BEINGs will be grouped
into a few families or professions; 
each family f has its own distinctive set ⊗2Q↓f⊗*
of questions which its members can answer.
Before detailing such a system, let us try to explain the motivations and the
mechanisms by which mathematicians operate.↑1↑1

.SSEC(Ideas About Doing Mathematics)
.WIDEN 6,8 SINGLE SPACE PREFACE 1

(i) The driving and pruning forces are (in decreasing order of importance) 
aesthetics/interestingness,
intuition, utility, analogy, inductive inference (based on empirical evidence), 
and deductive inference (formal methods).

(ii) Each of these forces is useful both in generating new conjectures, and
in assessing their acceptability.

(iii) If the essence of these ideas can be factored out into an explicit set
of BEINGs and utility functions, then that system can be used to
develop almost any branch of mathematics, at almost any level.

(iv) A protocol was taken, and indicates that the researcher must have a very
good set of strategies, organize them carefully, and use them wisely
to avoid getting bogged down in barren
pursuits. Some of this wisdom must pertain to precisely what is to be
remembered/recorded: a surfeit is bewildering, a shortage dangerous.

(v) Each mathematical concept should be represented in several ways, 
including declarative, operational, exemplary (especially boundary
examples), and intuitive.

(vi) A wide foundation of intuition, spanning several mathematical and 
real-world concepts, is prerequisite to sophisticated behavior in ⊗4any⊗*
branch of mathematics.  It is not "cheating" to demand some intuitive
concept of sets, before studying number theory, nor to demand some
intuitive understanding of counting before studying set theory, provided the
intuition is ⊗4opaque⊗* (can be used but not inspected in detail)
and fallible.
The more serious attack on the reliance upon divinely-provided 
intuitive abilities is
that the creators might stack the deck: might contrive just the right intuitions to
drive the worker toward making the "proper" discoveries.  The rebuttal is two-pronged:
first, one must assume the integrity of the creators; they must strive not
to anticipate the precise uses that will be made of the intuition functions. Second,
regardless of how contrived it was, if a small set of intuition models were found
which were sufficient to drive a researcher to discover a significant part of
mathematics, that alone would be an interesting discovery 
(e.g., educators would like to ensure
that children understood this core of images).

(vii) The vast amount of necessary initial knowledge can be 
generated from a much smaller
core of intuition and definite facts, using the same collection of
strategies and wisdom which also drive the discovery and the development
(those outlined above in (i)-(iv)).

(viii) The more basic the initial core concepts, the more chance there is that the 
research will go off in directions different from humans, the more
chance it will be a waste of time, and the more valid the test of the search-pruning
forces.
.SSEC(External Characteristics of a Proposed System)

Let us consider now what would be the characteristics of
a man-machine system which could be used  experimentally. 
The initial knowledge in the system will consist of (i) specific facts about
mathematics, reasoning, programming, and communication, (ii) strategies
for filling out parts of incomplete BEINGs, (iii) opaque functions
which simulate parts of Nature, and (iv) opaque judgment criteria
for aesthetics, interest, utility, complexity, etc.
The specific facts are
organized into 4 families of Beings; each family initially has about 35 BEINGs, and
each BEING has about 20 parts. The families are: 
Static (eg, sets), Active (eg, relation),
Static-Meta (eg, analogy), and Active-Meta (eg, prove).
For uniformity, the strategies form a fifth family of BEINGs, called Archetypical BEINGs.
A strategy BEING is simply a collection of facts for 
dealing with a particular
type of BEING part (e.g., the "Examples" 
BEING contains suggestions for filling in the
Examples part of any BEING).

The intuition functions represent the environment and are ⊗4opaque⊗*. 
For example, a model of a seesaw might exist, and the
system could play around at varying the weights on each side and their distance from
the fulcrum, and the seesaw function would explain which side sank and how fast.
This might be useful in getting an intuition about multiplication, substitution,
or symmetry.
	The quantity of this corpus appears large (about 3000 BEING-parts to
encode, each as a little LISP program), and it is of some interest to hope that
the very same techniques which lead to discovering new mathematical knowledge
later on might be able to "grow" this knowledge base from a much smaller core --
say a collection of 100 BEINGs with only a few parts filled in for each.
The first activity of such a system, then, would be ⊗4contemplative⊗*: the
interaction with the user would be minimal.
General strategies would interact with observations, and
new  concrete facts about its world would emerge, along with some new
specific tactics.
The system would also combine its intuitions to form plausible conjectures and,
where all terms have formal definitions, try to prove them.
The activities in this period are 
universal, not limited to any single
domain of mathematics.  

The user is considered slow and dangerously contradicatory, hence not a good channel
to obtain data in general.
But as the known information swells, the need for guidance also grows. 
At some point the
system may simply be swamped by a multitude of equally-mediocre alternatives to
investigate. 
It will then (abeit reluctantly) request  direction from
a human user, in what is to be an ⊗4assimilative⊗* phase. 
These teachings should be the
core definitions of a specific field, and of course should be based on what is 
already mastered. The first experiences could be in set theory, Boolean algebra,
abstract algebra, logic, or
arithmetic.  This will probably be the level finally attained by the actual system.

One higher mode of interaction is conceivable: that of a colleague in research.
In conjunction with a
human adviser, the system would propose and explore interesting new relationships,
decide which creations to name, explore the intuitive meanings of statements, etc.
Hopefully, the reader has balked, complaining that this sounds just like the earlier
phases. In fact, the system will not ring a bell and suddenly switch its activities;
it has no way of knowing that its discovery of PLUS is not new to Mankind.  
The driving and pruning forces in all phases are the same: use 
aesthetics and utility judgments to fill out parts of incomplete BEINGs.
If the guidance of the human turns out to be
important, however, then it will come as no surprise if
the flavor of the interactions changes as the system enters a realm unfamiliar
to the user.

The overall control flow would be a series of 
⊗4"Work on part p of BEING B"⊗* directives.
The driving/pruning forces would each time select the next (p,B) pair.
During the course of such
completions, new BEINGs might be called for (split off rich 
subparts of part of an already-exisiting BEING).  

The following ideas are fairly concrete, dealing
with realizing such a system:

(i) The system, if containing modules for each driving and pruning force,
should operate even if some of these forces have been
"turned off,"  so long as ⊗4any⊗* of the modules remain
enabled. For example, if all but
the formal manipulation knowledge is removed, the
system should still grind out
(simple) proofs. If all but the analogy and intuition modules are excised,
some plausible (but uncertain) conjectures should still be produced and
built upon. 
The converse situation should also hold: although still functional with any module
unplugged, the performance ⊗4should⊗* be noticably degraded. 
That is, while not indispensible, each module should nontrivially help the others.
For example,
the job of proving an assertion
should be made much easier by the presence of intuitive understanding. If
a constructive proof is available, the necessary materials will already be
sketched out for the formal methods to build upon.

(ii) The human working with the system has several roles. First, he must
determine what domain of mathematics is to be examined, what is to be
assumed as known, etc.  Second, he must guide the system, by suggestion
or discouragement, to avoid (probably) fruitless investigations, and to
concentrate on desirable topics.
Third, he might be called on as absolute authority, to provide a needed
fact (e.g., a theorem from another domain) at just the right time.
Ultimately, he might become a co-researcher, when and if the system is
operating in a domain unknown to him.

(iii) In what sense will the system justify what it believes? The aim is
not to build a theorem-prover, yet the leap from "very probable" to 
"certain" is not ignorable. 
Some sophisticated studies into this problem have
been done↑1↑2 and may prove usable. 
The mechanism for belief in each fact, its certainty, should be
descriptive (a collection of supporting reasons) with a vector of numerical
probabiities (estimated for each factor) attached. These numbers
would be computed at creation of this
entity, recomputed only as required.   The most fundamental entities may
have ⊗4only⊗* numerical weights. 
If the weight of any entity changes, no "chasing
around" need be done. Contradictions are not
catastrophic: they simply indicate that the reasons supporting each of the
conflicting ideas should be reexamined, their intuitive and formal
justifications scrutinized, until the "sum" of the ultimate beliefs in
the contradictory statements falls below unity, and until some intuitive
visualization of the situation is accepted.
If this never happens, then a problem really exists here, and might
have to be assimilated as an exception to some rule, might decrease the
reliability placed on certain facts and methods, etc.
This algorithm, whatever its details, should be embedded implicitly in the
control ⊗4environment⊗*; the system should not have the power to inspect or
modify it.

(iv) The communication between the system and the human should be in a
language suited to the particular role he is playing. Thus there can be 
some formal language, some traditional math notation language, some
pictorial language, etc.  Although efficiency will demand a fixed
syntax and semantics for each of these, a trial protocol has indicated
that the typical form of mathematical communication is well defined
(i.e., it should be feasible to construct formal languages in this
domain, for which the user will not need much prior training).

(v) The following diagram indicates the (traditional) logical progression
of domains in mathematics, and the system should be able to start almost
anywhere and move forward (following the arrows).
Movement backward might be possible, and in some cases may be quite smooth.
This is because the psychological progression does not mirror the logical
progression.
.BEGIN NOFILL  SKIP 1 SELECT 8 TURN OFF "α↑↓_" PREFACE 0 MILLS
.GROUP

Elementary Logic  ααα→  Theorem-Proving  ααααααααααααααα⊃
    ↑							~
    ~							~
    ~							~
    εααααααααααα→  Geometry  ααα→  Topology		~
    ~		    ~			~		~
    ~		    ~			~		~
    ~		    ↓			↓		~
    ~      Analytic Geometry       Algebraic Topology	~
    ~		  ↑  			↑		~
    ~             ~  			~		~
    ↓	          ~  			~		~
Boolean Algebra  αβα→    Abstract Algebra 		~
    ↑             ~       ~				↓
.ONCE TURN ON "α"
    ~	          ~       ~		  Program Verification
    ~	    Analysis      ↓				↑
    ~		   ↑     Concrete Algebra		~
    ~              ~      ↑				~
    ~		   ~      ~				~
    ↓		   ~      ~				~
Set Theory  ααα→  Arithmetic  ααα→  Number Theory	~
		      ~					~
		      ~					~
		      ↓					~
		Combinatorics  ←ααα→  Graph Theory  αααα$

.E

(vi) Advancement in field x
should be much swifter if field y is mastered already, regardless which
fields x and y represent.  An analogous statement applies to progress within any 
field, when other parts of it have been developed. 

(vii) To start in a particular field, there must be much 
intuition, and some definite facts, about each preceding ("⊗8αααα→⊗*"
in the diagram above)
domain of mathematics.  For this reason, the system is expected to start with
logic, set theory, Boolean algebra, or arithmetic, and move from one of these 
to another, or move along the arrows in the diagram. 
The progression to number theory is the tentative choice for an advanced thrust.

(viii) Since the precise strategies are so crucial, it might be
advantageous to allow them to evolve. This includes changing the system's
notion of interestingness as its experience grows. Such an ability is so slippery
that the system is tentatively planned ⊗4not⊗* to have much freedom here.
Intuitions and strategies may be inspected and changed, 
just like specific facts, but
the notions of how to judge interestingness, belief, safety, difficulty, etc. 
(plus all the algorithms for split-msecond estimating and updating these)
are fixed for
the system by its creator. If they are unsatisfactory, he must retune them.

(ix) It seems desirable to use a single representation for all of these: 
specific knowledge about objects (e.g., bag) and
operators (e.g, union); general knowledge about meta-objects (e.g., conjectures)
and meta-activities (e.g., prove, communicate).
A fifth category is the strategic information dealing with how to recognize,
interpret, fill in, modify, check, and work with the other types of knowledge.
A family of BEINGs will be designed for each of the five
knowledge categories; each family
will have its own set of BEING parts. The parts of a specific knowledge BEING
will relate all the various kinds of things one can know about a single
mathematical concept (Usage, Boundary examples, Name,...); the parts of a
strategy BEING S will contain guides for filling in part S of each 
specific information BEING.
This last statement was tricky: a strategy BEING is 
simply an expert on dealing with one
particular part of a group of other BEINGs. For this reason, we also call it an
⊗4archetypical⊗* BEING, and its name must coincide with the name of a part; occasionally,
it will be named B.π, which means that it is useful for dealing with part π of any
BEING in the B family of BEINGs.

(x)  It is ⊗4not⊗* desirable to have only one representation of knowledge in a 
system;
while multiple knowledge formalisms create interfacing difficulties, the advantages
of expressing a piece of information in the best-suited way is considered worth the
headaches of interfacing.   BEINGs are fine for storing structured information in an
accessable manner, but much of the system will be inaccessable. For example,
the "fixed" wisdom of how to home in on the most
relevant strategies at any given time can be stored in a more efficent
manner, completely opaque to the system, as implicit 
compiled meta-strategic Environment functions.

(xi) Control in the system will involve zeroing in on a relevant part of a relevant
BEING, then using strategies dealing with such a part to work on it. The proposed
control algorithm is tedious but not complicated.
Often the family of BEINGs is determined, then the subfamily, then the
specific BEING. The group of parts relevant is determined, followed by the
specific part. The specializing choice is typically made by the currently
available group. For example, after determining that one of the Proof
BEINGs is relevant, the system lets all the proof BEINGs fight it out and
decide which of them is most relevant. This diffusion of decisive power is
common in human activites but surprisingly rare in computer programs.
Let us suppose that somehow we have selected that part p of BEING b must be
filled in.
Strategies associated with that kind
of part for that family of BEING will then be run, and will attempt to
fill in the part p. This may result in new discoveries, in new BEINGs being
created, in failure, in fully filling in p, or in partially filling it in
but stopping because some new fact was encountered which might be more
interesting.

(xii) The basic mechanism is thus the filling in and the running of parts of BEINGs.
But BEING parts are generally procedural knowledge, so this task really means
automatic code synthesis. Knowledge is stored with an idea toward future usage,
both in where it is placed and how it is recorded.
This is the logical continuation of the usage-oriented storage originating in
PUP1↑4 and developed into BEINGs in PUP6 (Section 2 of this paper).

(xiii) The human user might be modelled within the formalism, by a
single BEING named USER which models a person (including his extremes
of absolute authority and dismal self-contradiction, of adaptability and fallability,
of creativity and impatience, etc.)
Its WORTH part could indicate the costs and 
desirability of  querying the user in any given situation.
Actual translations could be effected by efficient environmental 
functions called by this BEING, or by a subfamily of Communication BEINGs.

(xiv) A balanced distribution of intelligence ought to exist: related BEING parts which
are rarely accessed separately should be coalesced, and any single type of BEING part
used very heavily should be split. Notice that this theme has two quite different
realizations. During run time, this policy would refer to the contents held in
existing BEINGs' parts (e.g., when one part grows too large
and complicated, it may be replaced by a
list of pointers to new BEINGs). Before the system is actually created, however,
this policy means altering the proposed anatomy of BEINGs 
The runtime restructurings occur based on knowledge recently created by the
system; the planning-stage restructurings are now being based on results from
hand simulations of the system.  During runtime, the set of parts that
any specific BEING can ever have is fixed by the family (profession) to which he
belongs.

.SELECT 1

.SSEC(Details of the Proposed System)

.SSSEC(Organization of BEINGs Present in the System Initially)
.XGENLINES←XGENLINES-1

The value of all parts with the same name must be stored in a known format (which
can vary with the part name); all these formats are described in a single format.
Just as all BEINGs group into 5 families, so all parts fall into one of 4
major ⊗4part groupings⊗*.
All family members have the same set of parts names; all parts of a grouping
have some interrelated semantics. If the set of parts were ideally
orthogonal, one wouldn't have any meaningful parts groupings. There is an
⊗4advantage⊗* to the grouping, however: that of factoring. One needn't choose
between an array of 16 parts; rather, make a choice of one of four groupings,
followed by a choice of one of four specific parts depending on the grouping.

.BEGIN SELECT 6 NOFILL 

⊗2OBJECT BEINGS:   STATIC HOLDERS OF INFORMATION⊗*
 Primitive Containers 		Basic holders of information
   Ordered pair
   Variable
   Propositional constants		T,F
 Structures		Information containers subject to constraints (axioms)
   Hist			A list which also recalls all past insertions and deletions.
   List			As in LISP, built out of ordered pairs.
   Oset			A list with all repetitions of elements disallowed.
   Bag			A structure with no order, but repetitions are distinct.
   Set			No order, and no distinct repetitions allowed.
 Assertions		Statements claimed to be true
   Axioms		True facts which neither have nor need any formal justif.

⊗2ACTIVE BEINGS:   DYNAMIC PROPERTIES AND RELATIONS⊗*
 Operation		Transform a given argument into a new entity.
   Composition
   Insertion
   Deletion
   Convert-Struc		Transform a structure from one type to another.
   Substitute
  	  Assign	Substitute new value for old one in value part of a variable.
   Mapstruc		Replace each member of struc by result of applying given op.
   Reverse Ordered Pair
   Rule of Inference
   Disjunction
   Conjunction
   Negation
   Implication
   Unite		Join two data structures.
	  Union		Unite two sets.
   Cross-product
   Common-parts		What do given two data structures share in common?
	  Intersection		Common-parts of two given sets.
   Setdifference
   Put-in-Order
 Relation		Ordered pairs.
   Equality
   Membership		ε
   Containment		 ⊂
   Equivalence		  ≡
   Scope		 Territorial precedence of a declaration binding a variable.
   Quantification
	universal:  For all
	existential: There exists
	universally negative: Never
	existentially negative: Not always
	neither never nor always: For some but not for all
 Property	Confirm or deny, for any given object in the domain.
   Ordered
   Extreme
   Active.Operations		Properties of Active BEINGs.

.XGENLINES←XGENLINES-1

⊗2STATIC META BEINGS: OBJECTS WITH JUSTIFICATIONS⊗*
 Statement
   Statement of Generality
   Statement of Existence
 Non-justifiable
   Message
   Assumption
 Justifiable but probably unjustified
   Conjecture
   Bug
   Contradiction
   Analogy
 Fully justified
   Theorem
   Proof
   Counterexample
 Mathematica
   Mathematical Theory		Foundation + theorems relating foundation members.
	Foundation		Basis + axioms constraining basis members
		Basis		Primitive structures and operations on them
   Formal System

⊗2ACTIVE META BEINGS: ACTIONS WHICH AFFECT BEINGS⊗*
 Inference			Problems to find
   Find				search a space for a suitable element
   Select				choose the best element from given alternatives
   Guess				formulate a new conjecture
   Ellipsis			infer from examples; and so on; ...
   Analogize
   Conservation			including invariance, inertia, frame problem
   Examine			prior to attemping pf. or disproof; which is more likely?
 Test				Problems to prove
   Assume
   Define
   Prove
     Logically deduce
  	Prove directly
		Cases
		Backward chaining
	Prove indirectly
	Prove statements of generality
		Mathematical Induction
	Prove statements of existence
		Constructively prove existence
		Nonconstructively prove existence
   Disprove
	Constructively disprove
	Indirectly disprove
   Debug
 Communicate
   With the user
	Translation of English			into calls on relevant BEINGs.
	Translation into English		of what a BEING wants to ask.
	User model
   With other BEINGs			Languages.
 Relation Meta BEINGs  	  	Active Meta-BEING's which are more relations than ops.
   Isomorphism
   Categoricity

.XGENLINES←XGENLINES-1

⊗2ARCHETYPICAL BEINGS: BEINGS WHOSE NAMES ARE PART NAMES⊗*
 RECOGNITION GROUPING
   CHANGES		Is this rele. to producing the desired change in the world?
   FINAL  		What situations is this BEING rele. to bringing about?
   PAST			Where is this used frequently, to advantage?
   IDEN {not}{quick}	{fast} tests to see if this BEING is {not} currently referred to
 ALTER GROUPING
   GENERALIZATIONS	What is this a special case of? How to make this more general.
   SPECIALIZATIONS	Special cases of this? What new properties exist only there?
   BOUNDARY		What marks the limits of this concept? Why exactly there?
   DOMAIN/RANGE {not} Set of (what one can{'t} apply it to, what kind of thing one {never} gets)
   ORDERING(Complete)	What order should the parts be concentrated on (default)
   WORTH	Aesthetic, efficency, complexity, ubiquity, certainty, analogic utility, survival basis
   INTEREST		What special factors make this type of BEING interesting?
   JUSTIFICATION   Why believe this? For/intu. For thms and conjecs. What has been tried?
   OPERATIONS	associated with BEING. What can one do to it, and what ahppens then?
 ACT GROUPING
	   CHANGE subgrouping of parts
   BOUNDARY-OPERATIONS {not}  Ops rele. to patching {messing}up not-bdy-entities {bdy-entities}
   FILLIN	How to initially fill it in, when and how to augment what is already there.
   STRUCTURE 		Whether, When, How to retructure (or split) this part.
   ALGORITHMS		How to compute this function. Related to Repr.
	   INTERPRET subgrouping of parts
   CHECK   		How to examine and test out what is already there.
   REPRESENTATION		How should entities of this type be represented internally?
   VIEWS	How to view as an operator, function, relation, property, corres., set of tuples.
 INFO GROUPING
   DEFINITION		Several alternative formal definitions of this concept.
   INTU		Analogic interp., ties to simpler objects, to reality. Opaque.
   TIES   	Alterns. Parents/offspring. Analogies. Associated thms, conjecs, axioms, specific BEING's.
   EXAMPLES {not} {bdy}	Includes trivial, typical, and advanced cases of each type.
   CONTENTS       What is the value stored here, the actual contents of this entity.

.END

.SSSEC(Interactions among system components)

A rather specialized ⊗4environment⊗* exists to support these BEINGs. Encoded as
efficient opaque functions, the environment must oversee the flow of control
in the system (although the BEINGs themselves make each specific decision as to
who goes next). It must also include evaluations of belief, interest, supeficiality,
safety, utility; it must keep brief statistics on when and how each part of each
BEING is accessed; and the environment must maintain a rigidly-formatted
description of the Current Situation (abbreviated CS; this 
structure also includes summaries of recent system history).
When a part is big and heavily accessed, detailed records
must be kept of each usage (how, why, when, final result) of each ⊗4subpart⊗*.
Based on this, the part may be split into a group of new BEINGs, and the value
of the part replaced by a pointer to a list of these new BEINGs. 

The environment would have to accept the returning messages of the attempt to
deal with a certain part of a certain BEING. A success or a failure would mean
backing up to the last decision and re-making it
(usually the top-level "select (P,B) to work on next" decision).
An "interrupt" from a trial
would mean "here is some possibly more interesting info". The environment
must decide if it is; if not, it returns control to the interrupted process.
If so, it automatically switches to that part of that BEING (the part may
not be specified). Later, there will be no automatic return to the interrupted
process, but whatever sequence of decisions led to its initiation may very
probably lead there again.
Two tricks are planned here. One is a cache: each BEING will let  its
RECOG parts store the last value computed, and let each
such part have a quick predicate which can
tell if any feature of the world has changed which might affect this value.
If not, then no work is done; the old value is simply
returned. If x is interrupted,
an auxilliary development is begun, and then work on x should continue,
most of the decisions leading back to x will probably not involve any real
work, since most of the world hasn't changed. The second trick is that to
evaluate a part, one moves down its code with a cursor, evalling. When
interrupted, that cursor is left just at the point one wants to start at when
the work resumes.

New BEINGs are created automatically if, when a part is evaluated and a new entity
formed, it has sufficient interest to make it worth keeping by name.
Also, an existing part P of a BEING B may be replaced by a list of new BEINGs.
The details of when and how to do this restructuring of B.P are stored under the 
Structure part of the archetypical BEING whose name is P. The typical process is as follows:
The environment keeps loose checks on the size and usage of each part; if one
ever grows and eats up much time, it is carefully monitored. Eventually, its
subparts may partition into a set whose usage is nearly disjoint. If this
is seen, then the part is actually split into a new set of BEINGs.
If a new BEING doesn't live up to its expectations, it may be executed
summarily (overwritten and forgotten; perhaps enough is remembered to not waste
time later on the same concept).

One difference from PUP6 is that here the BEINGs are grouped into families.
Each family has its own set of parts (although there will be many parts present in
many families, e.g. Iden). For each family F there will be a fairly general BEING named
F. Under each part of F
is general information which, though not applicable to all BEINGs, is applicable to all
BEINGs belonging to family F.  Similarly, if P is a part name, then the BEING named P contains
information which is useful for dealing with part P of any BEING. There might also exist
an archetypical BEING named F.P, who would have special information for working with
part P of any BEING in family F.  There might even be a BEING called B.P, where B is
some specific BEING, with information that just deals with part P of B and any future
specializations of B. The information stored inside a part of a BEING, for example
the actual contents of B.P, would be 
code capable of computing
B's answer to the question P; the previously
mentioned archetypical BEING named B.P would contain strategies for dealing with such
answering code (how to fill it in, how to check it, etc.).  
To reiterate:   the contents of a part
are specific knowledge, a little program which can answer a specific query, whereas
the contents of the parts of an archetypical BEING are partially ordered sets
of strategies
for dealing with that part of that type of BEING (how to
extend it, what its structure is, and so on).
Notice we are saying that all the parts with
the same part name, of BEINGs in the same family, must all have the same structure.
This is one additional level of structure from the BEINGs proposed in PUP6.

The lower-level BEINGs will provide fast access to well-organized information.
The background environment provides the necessary evaluation services at
high speeds (though the system cannot meaningfully examine, modify, or add to
what environment functions the creators provide).
The BEINGs hold "what to think"; the environment implicitly controls "how to think".
The big assumption is that one may think creatively without knowing how his thought
processes operate; intelligence does not demand absolute introspection.

Common knowledge should in some cases be factored out. Possibilities:
(i) always ask a specific BEING, who sometimes queries a more general
one if some knowledge is missing; (ii) always query the most general
BEING relevant, who then asks some specific ones (This sounds bad);
(iii) ask all the BEINGS pseudo-simultaneously, and examine the
responders (this sounds too costly.) The organization of BEINGs into
hierarchical groupings reflects the spirit of (ii); 
their heterarchical equality↑8 favors (iii); yet
a BEING only
contains additions and exceptions to what its generalization contains,
so (i) is actually the dominant scheme now envisioned.

.SSSEC(Representation)

The theme of a BEINGs system is to distribute the understanding of knowledge among
all the parts of all the modules. Thus there will be many different ways in which
the system can claim to understand something. For example, it might be able to carry
out some activity (Algorithms), to formally discuss that activity (Definition), to
relate it to other activities it knows about (Ties), and even to give vivid intuitive
imagery to aid in visualizing the essence of the activity (Intuition).
Some of the knowledge present
initially will be stored in each of these forms.
The actual ways to represent the knowledge, especially
intuitive knowledge, are of some interest.  

The two broad categories of knowledge are definite and intuitive. To represent
the former, we employ (i) rules and assertions, (ii) BEINGs grouped into families,
and (iii) opaque Environment functions. To represent the latter, we employ
(i) abstract rules, (ii) pictures and examples, and (iii) opaque Environment functions.

Each currently popular formalism for representing knowledge
represents a point somewhere along (or very near to) the ideal
"intelligence vs. simplicity/speed" tradeoff curve.  Another way to
see this is to picture each representation as some tradeoff between
structure and uniformity, between declarative and procedural
formulations.  Each idea has its uses, and it would be unwise to
demand that any single representation be used everywhere in a given
system.  One problem with the alternative is how to interface the
multiple representations.  Usually this is enough to persuade
system-builders to make do with a single formalism.  The proposed
system will be pushing the limits of the available machinery in both
the time and space dimensions, and therefore cannot indulge in such
luxuries!  Knowledge used for different types of tasks must be
represented by the most suitable formalism for each task. 

BEINGs are higly structured, intelligent, but slow. Rules and
assertions are more uniform and swift, but frequently awkward. 
Compiled functions win on speed but lose on accessability of the
knowledge they contain.  Pictures and examples are universal but
inefficient in communicating a small, specific chunk of information. 

Let us now partition the types of tasks in our system among these
various representations.  The frequent, opaque system tasks (like
evaluating interestingness, aesthetic appeal, deciding who should be
in control next) can be programmed as compiled functions (the only
loss -- that of accessability of the information inside -- is not
relevant since they should be opaque anyway). 

The specific math knowledge has many sophisticated duties, including
recognizing its own relevance, knowing how to apply itself, how to
modify itself, how to relate itself to other chunks of knowledge,
etc. It seems appropriate that BEINGs be used to hold and organize
this information. The main cost, that of slowness, is not critical
here, since each individual chunk is used infrequently, and a wrong
usage is far more serious than a slow usage.  One final factor in
favor of using BEINGs here is that all the knowledge that is
available at the time of creation of a new BEING will find its way to the
right place; any missing knowledge will be conspicuous as a blank or
incomplete BEING part. 

The contents of each part of each BEING is composed of specialized rules,
assertions, and pointers to other parts and other BEINGs. The
knowledge may have to be altered from time to time, hence must be
inspectable and interpretable meaningfully and easily, so compiled
code is ruled out. To demand that each part of each BEING be itself a BEING
would trivially cause an infinite regress. Hence the reliance upon
"intermediate" representations and strategy BEINGs.

Communication between very different entities, for example between
the User and a BEING not designed to talk with him, are best effected via
a picture language and/or an examples language (from which the
receiver must infer the message). Such universal media are indicated when
communications falter; also useful for holding and relating intuitions of
the essences of the knowledge chunks stored in the BEINGs. 

The representation of intuitive knowledge as pictures and examples is
certainly not original.  Set theory books usually have pictures of
blobs, or dots with a closed curve around them, representing sets.
For our purposes, a set will be represented in many ways.  These
include pointer structures for ⊗6ε⊗*, ⊂, and their inverses; analytic
geometric functions dealing with sets as equations representing
regions in the plane; prototypical examples of sets; a collection of
abstract rules for simulating the construction and manipulation of
sets; and, finally, a set might be intuitively represented as a
square in the cartesian plane.  All these are in addition to the
definite knowlege about sets (definition, axioms and theorems about
sets, specific analogies to other concepts). 
Of course, each of the hundred or so BEINGs initially in the system should
have detailed, useful, multiple intuitive representations, just as SET does.

The notion of a fuzzy rule will remain fuzzy throughout this
paper. The basic idea is that of a production system, with left
sides that can latch onto almost anything, which eventually generate
lots of low-certainty results. These would augment some
BEING's intuition parts, and when trying to relate two given BEINGs which
both had such fuzzy abstract rules, one might try to "run" the
combined production system, or merely to "compare" the two systems. 
As with pictures and examples, the benefits of universality and
adaptability outweigh the inefficencies. 

Opaque simulations of (about a dozen) real-world situations is another important
component of the representation of intuitive knowledge. For example,
there might be a simulated jigsaw puzzle, with models of pieces,
goals, rules, hints, progress, extending, etc.  There will be a
simulated playground, with a seesaw model that will respond with what
happens whenever anything is done to either side of the seesaw. There
will be flamboyant models, like mountain-climbing; mundane ones like
playing with blocks; etc.  The obvious representation for these simulations
is compiled functions, which are automatically opaque. 


.SSSEC(Communication)

The work in this area consists of collecting English words and
grammatical constructions, of the kind found in various mathematics texts.
The next step is to exhaustively categorize all
words and phrases, and tie each one in to a BEING or a specific part. Also, some
fixed language scheme for communicating intuitive information must be devised.

.ONCE TURN ON "α"
Another ability which must be present is a DWIM-like↑9 recovery facility, 
tailored to
the kinds of errors one makes when discussing mathematics. For example, if someone
mentions "3+4", when + is defined only for rational numbers (a different symbol
α⊗ is emplyed for integers), then the error should be resolved by this simple bit of
psychology: "If an operation is applied incorrectly, and its real domain is in a very
closely analogous system, then map it back to find out which operator was really 
meant, and warn the speaker to be more precise in the future."

A third aspect is that of acclimatization to individual vocabulary and terminology.
(For example, is a "function" from A to B necessarily defined on all of A?)
One way to
acquire the user's preferences is during analysis of an error (as above); another way
is of course to allow the user to name the BEING himself (e.g., give him examples and 
intuition parts). His specific choices will go into the IDEN parts of the relevant
BEINGs; if there is any possibility of contradiction with standard usage, the entry will
be tagged with the user's name, for future reference.  Of course a single user may refer
to the identical concept by more than one name, but the system should never permit
him to refer to two different things by the same name. In such a case, if the user
stands firm on the new entity, the system has him rename the older entity.

.NOFILL

↓_Categories of Languages_↓

	English ↔ BEINGs calls
	  Standard Math Notation
		IMPLICATION
		SPECIFICATION
		COMBINATION
		OPERATION
		DEFINITION
		KNOWN RELATIONS
		ENTITIES
	  Fixed Formats for Quasi-English Meta-Comments, Questions, Hints
		ACTIVITIES
		RESTRICTED CONCEPTS
		INTELLECTUAL PROCESSING
		TIME AND SPACE REFERENCES
		INDEFINITES
		QUESTIONS
	  Fixed Language for Communicating Intuitive Concepts

	BEINGs ↔ BEINGs
	  The whole idea of BEING parts; especially: representation part of archetypical BEING's.
	  Language for Intuitive Communication
	  Language for Communication via Inference from Examples

.FAD
.NARROW 6,8
.SSEC(Projected Results)

There are several possible outcomes of all this. Even the most dismal
would yield some information about theory formation. At the optimistic extreme,
the system would yield new theorems in mathematics and new ways of approaching 
existing ones.

The ideal would be for the system to find a useful
redivision of some concepts, and new concepts overlooked by mathematicians.
The next best result would be the re-discovery and re-development of
existing mathematics, but only by being carefully led along the "right"
path. Even here, one should demand that it not be given so much to
start with that the
development is boringly direct and/or the
end results are obviously predictable. ⊗7(They are of course theoretically
predetermined, in the Turing machine sense).⊗*

Even if the system never gets beyond the  most elementary levels in each
field, that very failure will indicate for the first time a lower bound
on the magnitude of the theory formation problem. If our best efforts
produce only meager results, we will have to rethink the set of 
strategies over and over again. This might actually result in a better
final set of strategies than if the original set (chosen by introspection)
performs well!  

How much the strategies must adapt as the system proceeds is not known,
and will be learned during the experiment. It is hoped that such notions as
"how to use the strategies", interestingness, etc., need not evolve at all.
They will be tuneable only by the system's creators. 

If all the necessary initial facts, intuitions, and strategies can be generated from
a tiny hand-selected core of same, 
that alone is worth study. No one has investigated either
of the two ideas upon which this depends: 
that such a basis exists, and that no special
techniques are necessary to expand that core. Any difficulty here will indicate how
a self-contemplative process must differ from a purely investigative process.
A related experiment is to selectively remove parts of the "core", and see:
(i) if they are discovered anyway by the remainder, (ii) if so: when, why, how,
by whom, (iii) if not: which of the results that they led to are rediscovered anyway,
and which seem lost forever to the system?

.SSSEC(A Hypothetical Session)

Here is an example of how a discovery session might proceed with our proposed
system. It is unrealistic only in that the system should not be
expected to discover addition,
multiplication, exponentiation, primes, the unique factorization theorem,
and greatest common divisor,
all in one session.  
	In addition to the knowledge outlined earlier, assume that the system
has already discovered the notion COUNT, which maps any list (of length n)
into canonical form (perhaps a list of n NILs), the notions of Associativity
and Commutivity, the concept of a Function, of Inverse, and of Successor.
Many orderings of activities, and ways of interacting, must be
possible.  One typical sketch of its actions might be as follows; note
the minimal interaction with the user.

.BEGIN FILL SELECT 6 PREFACE 1 SINGLE SPACE WIDEN 6,8 INDENT 0,4,0

1. SYSTEM: Considering the composition COUNT * APPEND. Abbreviated CA.
Domain is {(x,y) | x is a list, y is a list}
Range is { z | z is a list in canonical form}
Examples are  CA( NIL, NIL) = NIL;  CA( x, NIL) = COUNT(x) = CA(NIL, x);
CA((a b),(c)) = (NIL NIL NIL) = CA((c), (a b));  etc.

2. SYSTEM: Conjecture that CA is commutative; intuitively: walk around to the other
side of the combination, answer is only dependent on how far you walk;
formally: derives from the lemma COUNT(APPEND((e),L)=COUNT(APPEND(L,(e)).
Lemma is proved by induction on L (using NIL as base step and CONS as incrementer).

3. SYSTEM: Conjecture that CA is associative; intuitively: because APPEND is associative;
formally: derives from the Lemma COUNT(APPEND(x,y))=APPEND(COUNT(x),COUNT(y))
and the associativity of APPEND.  Lemma proven by double induction on x and y.

4. USER (interrupting): What are the identity element of CA?

5. SYSTEM: Notice that NIL is both a left and right identity for CA. 
Interesting because CA(NIL,NIL)=NIL=the identity of the function APPEND. 

6. USER (interrupting): What are you trying to do now?

7. SYSTEM: It is very desirable to have a function operate on entities in
a given domain and return a value in that same domain. One way to do this
is by restriction.
So the function
COUNT * APPEND is considered restricted to apply only to pairs of canonical lists
(also called ⊗4numbers⊗*. 
N ≡ range(COUNT) ≡ the natural numbers ≡ the set of all canonical lists.)
Thus we consider CA: NxN→N.

8. USER: Try to relate this composition to the known function SUCCESSOR.

9. SYSTEM: Notice that SUCCESSOR is the COUNT of the APPEND of a set and a singleton,
so SUCCESSOR(COUNT(x))=CA(x,y) iff y is a singleton set (i.e., iff COUNT(y)=(NIL)).
We abbreviate (NIL) as 1. Considering CA restricted as in (7), x and y are in N,
so  SUCCESOR(x)=CA(x,y) iff y=1.

10. SYSTEM: This composition CA is worth saving.  Give it a meaningful name, user...

11. USER: Call it PLUS.

12. SYSTEM: So our last statement would read (∀xεN) SUCCESSOR(x) = PLUS(x,y) iff y=1.

13. SYSTEM: True range of PLUS is all of N.

14. USER: Unclear; please justify that to me.

15. SYSTEM: Since SUCCESSOR(x) can range over all nonzero numbers, so can
PLUS(x,1).  Also, notice that PLUS(0,0) is 0. So PLUS can assume any value in N. 

16. SYSTEM: Interesting corollary is that any number can be viewed as some unique
repeated PLUSsing of 1 (starting from 0=NIL). 
In particular, view PLUS as operating on a BAG. 
Then any number n is PLUS of a bag of 1's,  whose COUNT is n.
That is, ∀nεN. ∀b of type BAG.  [(CONVERT-TO-SET(b)={1}) ∧ (COUNT(b)=n)] iff n=PLUS(b).

17. SYSTEM: This suggests we change our canonical representation of numbers, from a list
of NILs to a list of (NIL)s. That is, from a list of zeros to a list of ones.

18. SYSTEM: PLUS is thus repeated SUCCESSOR-ing, and is interesting. 
What would it mean to do repeated PLUS-ing?  
That is, consider a function M:NxN → N, where
M(x,y) is the same as doing PLUS on a bag conaining y numbers, each of them being x.
So M(x,y) ≡ PLUS(x,x,...,x), where COUNT(x,x,...,x)=y.

19. SYSTEM: M is singlevalued, with domain NxN and range N. M is associative and commutative.
M(x,1) = x = PLUS(x,0), so the distinguished elements 1,0 are the identities
of M, PLUS, respectively. This is also a good sign. Name for M, please...

20. USER: Call it TIMES.  Try to see how TIMES can be directly interpreted in the 
language of sets. 

21. SYSTEM: It seems that TIMES(x,y) means one has a set with x elements, each of 
which is a set with y elements, and one is removing the boundaries of the inner
sets, then counting the whole collection.  The commutativity is clearly seen
by arranging the elements into a matrix of x rows and y columns; turning
this sideways results in a matrix of y rows and x columns;
but obviously the number of objects in toto has been conserved.

22. SYSTEM: Considered  PLUS(x, TIMES(y,z)). Worked a while, then gave up.
Low interest: PLUS(y,TIMES(x,y)) = TIMES(SUCCESSOR(x),y) = TIMES(PLUS(x,1),y).

23. SYSTEM: Considered PLUS(TIMES(x,y), TIMES(u,v)). Again, the only result noticed is
when x=u. Then PLUS(TIMES(x,y),TIMES(x,v)) = TIMES(x, PLUS(y,v)). 
This was the very next composition to be investigated, TIMES * PLUS.  
This is quite coincidental, hence interesting. Name this rule for me, user...

24. USER: Call it distributivity.  Are PLUS or TIMES 1-1? Is TIMES onto?

25. SYSTEM: The commutativity of PLUS and of TIMES indicate how to show that they
are not 1-1. PLUS↑-↑1(3) contains (2,1), (1,2), (3,0), and (0,3), which shows
that it isn't even unique 
to within rearrangements of the arguments, viewing PLUS as operating on a BAG.
Similarly for TIMES↑-↑1(4), which contains (1,4) and (2,2).
TIMES(1,x)=x for any xεN, so TIMES is onto N.
Consider now the behavior of different ways of computing their inverses (as relations).
PLUS↑-↑1(a)={zεN |  ∃yεN. PLUS(y,z)=a}. 
But then PLUS↑-↑1 is just the same as ≤; that is,  u≤v iff uεPLUS↑-↑1(v).
Analogously, we find that u|v iff uεTIMES↑-↑1(v).

26. USER: Consider statements involving Ordering as well as PLUS and TIMES.

27. SYSTEM: PLUS(x,y) ≥ x.  TIMES(x,y) ≥ PLUS(x,y) iff x and y are > 0.
TIMES(x,y) is usually bigger than PLUS(x,y); the exceptions are if x or y 
is 0 or 1, or if x=y=(NIL NIL). Thus 2=(NIL NIL) is distinguished now.

28. SYSTEM: Higher order operations are contructed, extending SUCCESSOR→PLUS→TIMES→...
E(x,y) is defined as TIMES operating on a bag of x elements, each of them a y. 
But at this point, associativity and commutativity fail, so there is no
reason to probe too hard. The only relationships noticed are that
TIMES(E(x,y), E(x,z)) = E(x, PLUS(y,z)), and also E(E(x,y),z) = E(x, TIMES(y,z)).  

29. SYSTEM: Rate of drop of interest in E, compared to SUCCESSOR, PLUS, TIMES is huge.
Dissuades me from pursuing higher order constructed operations.

30. SYSTEM: Although the inverses of PLUS and TIMES are not singletons, hence the inverses
are not functions, the COUNT of these sets may follow some regular pattern. 
COUNT * TIMES↑-↑1 is the number of ways to express a number as a product
of two numbers. TIMES↑-↑1 seems always to include the number and 1, as one pair.
Conjecture: (∀xεN)  (x,1) ε TIMES↑-↑1(x), and (1,x) ε TIMES↑-↑1(x).
Proof is of course that TIMES(x,1)=x=TIMES(1,x).
Corollary: COUNT*TIMES↑-↑1(1) = 1;  (∀x>1) COUNT*TIMES↑-↑1(x) ≥ 2.

31. SYSTEM: Interesting to consider the subset P of N defined as {x>1 | COUNT*TIMES↑-↑1(x)=2}.

32. USER: Why is this interesting?

33. SYSTEM: At the moment, we have the known fact f(x)≥y; try to pin down extreme cases,
those x for which f(x) is precisely equal to y. f is COUNT*TIMES↑-↑1, in the current
case, and y is 2.

34. USER: Call that composition PAIRWISE-FACTORINGS, or just FAC for short.
Call the set P, of extreme numbers under FAC, PRIMES.

35. SYSTEM: Syntactic transformation: PRIME is the predicate which means "is in PRIMES".
TIMES may also be viewed as operating on a BAG; in this sense, TIMES↑-↑1 would 
return all possible bags (of any length) whose product is the given number. 
In this case, (30) just says COUNT(TIMES↑-↑1(x)) ≥ 1. 
Some special notation is used to indicate that any number of 1's can be added
to any of the bags returned; thus we eliminate all extraneous 1's always.
The extremes now are just 1 and PRIMES.   
I want a new name for this new interpretation of TIMES↑-↑1.

36. USER: Call it FACTORS.

37. SYSTEM: Conjecture: FACTORS(x) always seems to contain a bag containing only
primes, and only one such bag. Proof of existence is by contradiction,
using the lemma  ¬PRIME(x) → ∃(u,v)εTIMES↑-↑1(x) s.t. 1<u<x, 1<v<x.
Uniqueness is by contradiction, using the lemma 
(∀a,bεN, xεPRIMES). x|TIMES(a,b) iff x|a or x|b.

38. USER: Call this the unique factorization theorem. This is very important.

39. SYSTEM: PLUS * UNION * TIMES↑-↑1 is the sum of all the divisors of the number.
<Considering those numbers for which this is <,=,> itself, we get 
superior, perfect, and inferior numbers>.
Similarly, consider COUNT * UNION * TIMES↑-↑1, the total number of factors of a number. 
This will always range from SUCCESSOR of that number to (almost up to) TIMES of that
number and itself. Those at the low end are the PRIMES. Those near the high end are
not so well grouped, and may not be named.

40. USER: Consider comparing TIMES↑-↑1 collections from two numbers.

41. SYSTEM: Clearly UNION * TIMES↑-↑1(x) is a subset of UNION * TIMES↑-↑1 (TIMES(x,y))
for any nonzero y.  When does equality occur? Some cases are when
y is 1, when y is a member of the first set. Trying to see if these are all.
I give up. Intuitively, these are all. Can rely on this conjecture anyway.

42: SYSTEM: Switching to comparing the intersection of TIMES↑-↑1 of two numbers.
That is, what factors do the two numbers have in common?   
Studying this for many cases... 
Seems that this intersection set is UNION * TIMES↑-↑1 of the largest member
of the intersection set. That is, the largest common factor determines all the others!
This is worth a name...

43. USER: Call it GCD, for Greatest Common Divisor.

44. SYSTEM: The GCD of a prime and any number is either 1 or the prime, 
and the second case occurs iff the prime is a factor of the second number.
In general, two  numbers may have GCD 1 with neither being prime. 
I now explore this... <relative primeness>
	
.END

.SSSEC(Synthesis)

Before closing, a brief review is in order. We began by examining why
biological entities dominate Earth, progressed to observing cooperating
human experts, and finally abstracted out a manageable set of design
constraints for a viable system. 
These were: discrete modules containing interrelated knowledge on very
specialized topics, each with the same anatomy but with a different area of
expertise, capable of querying, answering, and reproducing.

The first implementation, in the domain
of Automatic Programming, was partially successful. The difficulties
promted us to choose a new domain (Elementary Number Theory Research) and weaken
our constraints (uniform anatomy only within each family).
The role of knowledge modules is central to the new system, but not universal: 
wherever a more efficient representation of knowledge is possible, it is employed.

.ASEC(References)
.GROUP SKIP 1
.BEGIN  FILL  SPACING 0 MILLS  PREFACE 10 MILLS  WIDEN 6,8  INDENT 0,5,0

↑1 C. Hewitt, "A Universal Modular ACTOR Formalism for
Artificial Intelligence," ⊗43rd International Joint Conference
on Artificial Intelligence⊗*, 1973, pp. 235-245.

↑2 P. Winston, ⊗4Learning Structural Descriptions
from Examples⊗*, Ph.D. thesis, Dept. of Electrical Engineering,
TR-76, Project MAC, TR-231, Artificial Intelligence Laboratory,
Massachusetts Institute of Technology, Cambridge, Massachusetts,
September, 1970.

↑3 C. G. Hempel, ⊗4Fundamentals of Concept Formation in
Empirical Science⊗*, University of Chicago, Chicago, Illinois,
1952.

↑4 C. Green, R. Waldinger, D. Barstow, R. Elshlager, D. Lenat, B. McCune, D. Shaw,
L. Steinberg,
"Progress Report on Program-Understanding Systems", ⊗4SAIL Memo AIM-240,
CS Report STAN-CS-74-444,⊗* Artificial Intelligence Laboratory,
Stanford University, August, 1974.

↑5 W. A. Woods and J. Makhoul, "Mechanical Inference
Problems in
Continuous Speech Understanding, ⊗4Third International Joint Conference
on Artificial Intelligence⊗*, 1973, pp. 200-207.

↑6 R. Floyd, "Toward Interactive Design of Correct 
Programs", ⊗4IFIP⊗* 1971, V. 1, pp. 7-10.

↑7 D. Lenat, "Synthesis of Large Programs from Specific Dialogues",
⊗4Proceedings of the Symposium on Proving and Improving Programs⊗*, 
Institut de Recherche d'Informatique et d'Automatique, July, 1975.

↑8 P. Winston, ed., "New Progress in Artificial Intelligence",
⊗4MIT AI Lab Memo AI-TR-310⊗*, June, 1974. 
Note especially the summaries of work on Frames,
Demons, Hacker, Heterarchy, Dialogue, and Belief.

↑9 W. Teitelman, ⊗4INTERLISP Reference Manual⊗*, XEROX PARC, 1974.  Use was also
made of features of CLISP, QA4 (J. Rulifson), and QLISP (R. Reboh and E. 
Sacerdoti).

↑1↑0 R. B. Kershner and L. R. Wilcox, ⊗4The Anatomy of Mathematics⊗*, The Ronald
Press Company, New York, 1950.

↑1↑1 J. Hadamard, ⊗4The Psychology of Invention in the Mathematical
Field⊗*, Dover Publications, New York, 1945.

↑1↑2 R. Hilpinen, "Rules of Acceptance and Inductive Logic", ⊗4Acta
Philosophica Fennica⊗*, Fasc. 22, North-Holland Publishing Company,
Amsterdam, 1968. Also see J. Pietarinen, "Lawlikeness, Analogy, and
Inductive Logic", in Fasc. 26 of the same journal, 1972.
.END


.ASSEC(Acknowledgements)

The ideas and the system described are built upon recent researches. Many
hours of creative discussions were equally important.
In particular, the author  acknowledges the contributions by
C. Green, A. Cohn, R. Waldinger,
D. Shaw, and E. Sacerdoti.
Computer time for the research was generously provided by the Artificial
Intelligence Center of SRI.

.EVERY HEADING(,,)
.EVERY FOOTING(,,)
.PORTION CONTENTS
.NOFILL
.NARROW 6,8
.BEGIN CENTER


.SELECT 5
DUPLICATION OF HUMAN ACTIONS
BY AN INTERACTING COMMUNITY OF KNOWLEDGE MODULES

.SELECT 2

Douglas B. Lenat

Artificial Intelligence Laboratory
Stanford University




.END
.PREFACE 10 MILLS
.TURN ON "{∞→"
.NARROW 7,7
.RECEIVE

.CENTER



.SELECT 7
Mr. Douglas B. Lenat
Artificial Intelligence Laboratory
Computer Science Department
Stanford University
Stanford, California 94305, U.S.A.
.SELECT 1




Suggested running head:  ⊗4↓_Interacting Knowledge Modules_↓⊗*




.SELECT 7
{DATE}
.PAGE←0
.SELECT 1